Three major extensions to Kirkpatrick's point location algorithm
- 23 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 112-121
Abstract
Presents three extensions to D.G. Kirkpatrick's (1983) point location algorithm. The extensions revolve around major focuses in the point location problem, namely the location of close successive query points and the dynamic and persistent implementations. The solutions described in this paper include (a) an algorithm that requires O(1) query time for reasonably close successive query points, with O(N) space bound and O(N) time to construct the search structure; (b) a dynamic implementation that require O(N) space, O(log N) query time and O(log N) update time; and (c) a persistent implementation of the same complexity as the dynamic interpretation. Two methods for modifying the search structure (the /spl Kscr/-structure) dynamically and persistently are also discussed. The space requirements and query times of the dynamic and persistent methods are identical to their static counterparts. To affirm the practicality, conceptual simplicity and efficiency of the new methods, we implemented all these extensions, performed computational tests and compared them with other alternative schemes. The results reflect the expected efficiencies of the underlying design.Keywords
This publication has 25 references indexed in Scilit:
- Dynamic Point Location in General SubdivisionsJournal of Algorithms, 1994
- New Results on Dynamic Planar Point LocationSIAM Journal on Computing, 1992
- An incremental reconstruction method for dynamic planar point locationInformation Processing Letters, 1991
- Dynamic trees and dynamic point location1991
- Dynamic planar point location with optimal query timeTheoretical Computer Science, 1990
- Fully Dynamic Point Location in a Monotone SubdivisionSIAM Journal on Computing, 1989
- Planar point location using persistent search treesCommunications of the ACM, 1986
- Some methods of computational geometry applied to computer graphicsComputer Vision, Graphics, and Image Processing, 1984
- A new point-location algorithm and its practical efficiency: comparison with existing algorithmsACM Transactions on Graphics, 1984
- A New Approach to Planar Point LocationSIAM Journal on Computing, 1981