Have partition trees ever been implemented?

Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, and most recently Timothy Chan:


It sounds crazy to me that these have never been implemented, but googling turned up no implementations that anyone has ever reported on.

  • $\begingroup$ Where is that quote from? My PDF reader doesn't find it in the T. Chan paper your linked to. $\endgroup$
    – jbapple
    Commented Oct 4, 2014 at 0:37
  • $\begingroup$ It's from a manuscript, not Chan's paper. I just want to verify this as thoroughly as possible before it gets published. $\endgroup$
    – Pat Morin
    Commented Oct 4, 2014 at 1:00
  • 6
    $\begingroup$ I do not know the context of this question, but: (1) If you are reviewing a manuscript, I do not think it is okay to share part of the manuscript under review like this. (2) A paper should not make a claim like that because even if it is true, it is not verifiable. For example, no one can rule out the possibility that someone has implemented them as a personal project and never bothered to share it publicly. $\endgroup$ Commented Oct 4, 2014 at 12:44
  • 1
    $\begingroup$ Thanks for the helpful advice. It's a manuscript of a thesis written by my student. I would probably rephrase as: despite searching thoroughly, we are unaware of any implementations of partition trees. (Searching thoroughly is what I'm doing now, partly with this question.) $\endgroup$
    – Pat Morin
    Commented Oct 4, 2014 at 16:53
  • 2
    $\begingroup$ Could you simplify the question by removing the quote from the manuscript? Currently your post implies two questions (neither of which is explicitly stated): (1) How should I check the veracity of the claim that partition trees have never been implemented? Answer: You should not. (2) Do people know any implementations of partition trees? I do not know the answer to this part, but I think it is fine as a question. The only problem with (2) is no one can say “no” to that question, but you can infer it after some time if no one comes up with an implementation. $\endgroup$ Commented Oct 5, 2014 at 10:16

1 Answer 1


By the definition in the linked paper on page 5, the statement is wrong. Binary space partition (BSP) trees have been used for decades on computer graphics to speed up spatial queries, as have quadtrees and octrees. K-d trees are used extensively in machine learning to speed up nearest-neighbor searches. If you squint just a little, decision trees also fit the general definition.

  • 2
    $\begingroup$ Yes, I was aware of that. What I haven't found, though, is any implementation of a BSP tree for point sets that does any of the fancy stuff required to also keep its stabbing number close to O(sqrt(n)). $\endgroup$
    – Pat Morin
    Commented Oct 6, 2014 at 15:17
  • 3
    $\begingroup$ These aren't partition trees in the sense that the question is asking. I think the OP is specifically looking for data structures for half space range searching. $\endgroup$
    – Mikola
    Commented Nov 13, 2014 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.