A note on point location in arrangements of hyperplanes. (English) Zbl 1177.68241
Summary: We give an algorithm for point location in an arrangement of \(n\) hyperplanes in \(E^d\) with running time \(\text{poly}(d,\log n)\) and space \(O(n^d)\). The space improves on the \(O(n^{d+\varepsilon})\) bound of Meiser’s algorithm [S. Meiser, Inf. Comput. 106, No. 2, 286–303 (1993; Zbl 0781.68121)] that has a similar running time.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
Citations:
Zbl 0781.68121References:
| [1] | Chazelle, B., Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom., 9, 145-158 (1993) · Zbl 0784.52018 |
| [2] | Clarkson, K. L., A probabilistic algorithm for the post office problem, (Proceedings 17th Annual ACM Symposium on Theory of Computing (STOC) (1985)), 175-184 |
| [3] | Clarkson, K. L., New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195-222 (1987) · Zbl 0615.68037 |
| [4] | Matoušek, J., Cutting hyperplane arrangements, Discrete Comput. Geom., 6, 385-406 (1991) · Zbl 0765.68210 |
| [5] | Meiser, S., Point location in arrangements of hyperplanes, Inform. and Control, 106, 286-303 (1993) · Zbl 0781.68121 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
