<p>By the definition in the linked paper on page 5, the statement is wrong. <a href="http://en.wikipedia.org/wiki/Binary_space_partitioning" rel="nofollow">Binary space partition (BSP) trees</a> have been used for decades on computer graphics to speed up spatial queries, as have <a href="http://en.wikipedia.org/wiki/Quadtree" rel="nofollow">quadtrees</a> and <a href="http://en.wikipedia.org/wiki/Octree" rel="nofollow">octrees</a>. <a href="http://en.wikipedia.org/wiki/K-d_tree" rel="nofollow">K-d trees</a> are used extensively in machine learning to speed up nearest-neighbor searches. If you squint just a little, <a href="http://en.wikipedia.org/wiki/Decision_tree" rel="nofollow">decision trees</a> also fit the general definition.</p>

CC BY-SA 3.0
2014-10-06T15:17:49.403Z
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)).
Pat Morin
CC BY-SA 3.0
2014-11-13T18:06:35.667Z
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.
Mikola
CC BY-SA 3.0
2014-10-06T11:20:34.063Z
2014-10-06T11:20:34.063Z
Neil Toronto
<p>Have partition trees ever been implemented?</p>

<p>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:</p>

<p><a href="https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf">https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf</a></p>

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

CC BY-SA 3.0
2014-10-04T00:37:52.330Z
Where is that quote from? My PDF reader doesn't find it in the T. Chan paper your linked to.
jbapple
CC BY-SA 3.0
2014-10-04T01:00:52.830Z
It's from a manuscript, not Chan's paper.  I just want to verify this as thoroughly as possible before it gets published.
Pat Morin
CC BY-SA 3.0
2014-10-04T12:44:12.600Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-04T16:53:11.647Z
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.)
Pat Morin
CC BY-SA 3.0
2014-10-05T10:16:31.570Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2015-01-13T19:22:40.507Z
I had implemented cuttings long time ago. The constants involved are not great (even in the plane), and in practice you would need monstrously large input to have any chance to be competitive. On the other hand, simple heuristics (say, sort the point by z-order and break them into natural clusters), would work reasonably well. Anyway, if you do not care about efficiency too much, a partition can be constructed via LP relaxation and rounding. You would lose log(n) over the optimal partition, but nobody should care. It is possible that by being clever one could get efficient implementation.
Sariel Har-Peled
<ds.data-structures><implementation><computational-geometry>
Implementation of partition trees?
Pat Morin
# Implementation of partition trees?

(Asked by: username_0 on 2014-10-03)

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:

<https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf>

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

**Tags:** ds.data-structures, implementation, computational-geometry

> **Comments:**
> **username_1**: Where is that quote from? My PDF reader doesn't find it in the T. Chan paper your linked to.  
> **username_0**: It's from a manuscript, not Chan's paper.  I just want to verify this as thoroughly as possible before it gets published.  
> **username_2**: 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.  
> **username_0**: 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.)  
> **username_2**: 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.  
> **username_3**: I had implemented cuttings long time ago. The constants involved are not great (even in the plane), and in practice you would need monstrously large input to have any chance to be competitive. On the other hand, simple heuristics (say, sort the point by z-order and break them into natural clusters), would work reasonably well. Anyway, if you do not care about efficiency too much, a partition can be constructed via LP relaxation and rounding. You would lose log(n) over the optimal partition, but nobody should care. It is possible that by being clever one could get efficient implementation.  

---

## 1 answers

### Answer by username_4 on 2014-10-06. Score: 3

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

> **Comments:**
> **username_0**: 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)).  
> **username_5**: 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.  

---

