I really doubt it because any point can have a median drawn through it. Remember, the median can go in any direction. For any point, you can find some angle to draw a line through that point that will separate all other points of that color into two equally-sized groups. So if it's a tree structure, it's not a standard one where divisions are made parallel to the axis of the graph. | [reply] |
I've not yet convinced myself that this is soluble in the general case.
In the 2D case, if all the points in both groups have one coordinate in common, and there are an odd number of points in each group or in the more general case of all the points lying on a straight line at any arbitrary angle.:
+-----------+ +-----------+ +-----------+
| . | | | | . |
| x | | | | . |
| x | | | | . |
| . | |.xx . x . | | x |
| . | | | | x |
| x | | | | x |
+-----------+ +-----------+ +-----------+
Unless you consider the line passing through all the points satisfies the criteria of having an equal number of each type of point on either side; ie. none?
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l] |
Exactly. If all points lie on the same line, that line is the correct line.
Btw, where I am so far, I may actually end up using some kind of (VERY nonstandard) tree to get from n^2 to n*lg(n). That would make you right :-)
| [reply] |
(1b) I have an n*lg(n) solution for 2-D. Sorry, BrowserUK: I was SO wrong in saying no tree. My solution (which I have not coded) uses a PR quadtree. My solution is certainly not the only approach that will work.
(1c) I have no idea (yet) how this might be brought up to O(n), nor do I have a clue (yet) how to prove it impossible.
(2a) Also, while a PR quadtree can be used in 3D, my approach does not extend easily to 3D. More thought required.
Question: For a puzzle, ought I post pseudocode/code on completion, or is it polite to instead leave the solution unposted, giving others the fun of solving it?
Keep chuggin', guys! Nothing quite so rewarding as solving a tough puzzle! | [reply] |
