Fully dynamic techniques for point location and transitive closure in planar structures
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 558-567
- https://doi.org/10.1109/sfcs.1988.21972
Abstract
It is shown that a planar st-graph G admits two total orders on the set V union E union F, where V, E, and F are, respectively, the sets of vertices, edges and faces of G, with mod V mod =n. An O(n) space data structure for the maintenance of the two orders is exhibited that supports an update of G (insertion of an edge and expansion of a vertex, and their inverses) in time O(log n). This data structure also supports transitive-closure queries in O(log n). Moreover, planar st-graphs provide the topological underpinning of a fully dynamic planar point location technique in monotone subdivisions, which is an interesting (unique) specialization of the chain method of Lee-Preparata (1977). While maintaining storage O(n) and query time O(log/sup 2/ n), insertion/deletion of a chain with k edges can be done in time O(log/sup 2/ n+k), and insertion/deletion of a vertex on an edge can be done in time O(log n).Keywords
This publication has 20 references indexed in Scilit:
- Algorithms for plane representations of acyclic digraphsTheoretical Computer Science, 1988
- Finding paths and deleting edges in directed acyclic graphsInformation Processing Letters, 1988
- Amortized efficiency of a path retrieval data structureTheoretical Computer Science, 1986
- A unified approach to visibility representations of planar graphsDiscrete & Computational Geometry, 1986
- Computational GeometryPublished by Springer Nature ,1985
- A dichromatic framework for balanced treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Location of a Point in a Planar Subdivision and Its ApplicationsSIAM Journal on Computing, 1977
- Applications of a planar separator theoremPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- On the vector representation of the reachability in planar directed graphsInformation Processing Letters, 1975