On the Exact Worst Case Query Complexity of Planar Point Location
✍ Scribed by Raimund Seidel; Udo Adamy
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 241 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
What is the smallest constant c so that the planar point location queries can be Ž . Ž . answered in c log n q o log n steps i.e., point᎐line comparisons in the worst 2 Ž case? M. T. Goodrich, M. Orletsky, and K. Ramaiyer 1997, in ''Proc 8th ACM-Ž . . SIAM Symp on Discrete Algorithms SODA ,'' pp. 757᎐766 showed that c s 2 is possible using linear space and conjectured this to be optimal. We disprove this conjecture and show that c s 1 can be achieved. Moreover by giving upper and lower bounds we show that without space restrictions the worst case query complexity of planar point location differs from log n q 2 log n ' 2 2 Ž . Ž . at most by an additive factor of 1r2 log log n q O 1 . For the case of linear ' 2 2 Ž 1r 4 . O log n .