Partition Tree

2-Dimensional Case

Source: Computational Geometry: Algorithms and Applications

Let be a set of points. A simplicial partition for is a collection , where and is a triangle containing . For some line , the crossing number is the number of triangles in crossed by . A simplicial partition is fine if for every .

Theorem 1

Info

For any set with points and parameter , a fine simplicial partition of size and crossing number exists. Furthermore, for any , this partition can be computed in .

TODO: Find proof. Martousek (?)