A note on point location in arrangements of hyperplanes |
| |
| Authors: | Ding Liu |
| |
| Affiliation: | Department of Computer Science, Princeton University, Princeton, NJ 08544, USA |
| |
| Abstract: | We give an algorithm for point location in an arrangement of n hyperplanes in Ed with running time poly(d,logn) and space O(nd). The space improves on the O(nd+ε) bound of Meiser's algorithm [Inform. and Control 106 (1993) 286] that has a similar running time. |
| |
| Keywords: | Computational geometry Point location Hyperplane arrangements |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
