Abstract
We prove the existence of linear size binary space partitions for sets of objects in the plane under certain conditions. In particular, we construct linear size binary space partitions for sets of fat objects, for sets of line segments where the ratio between the lengths of the longest and shortest segment is bounded by a constant, and for homothetic objects. For all cases we also show how to turn the existence proofs into efficient algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 317-333 |
| Number of pages | 17 |
| Journal | Computational Geometry |
| Volume | 8 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 1997 |
Fingerprint Dive into the research topics of 'New results on binary space partitions in the plane'. Together they form a unique fingerprint.
Cite this
Berg, de, M., Groot, de, M. M., & Overmars, M. H. (1997). New results on binary space partitions in the plane. Computational Geometry, 8(6), 317-333. https://doi.org/10.1016/S0925-7721(97)00008-4