Michael T. Goodrich, Roberto Tamassia  Home/Search
Context Related
| jhu.edu/~goodrich/pubs/point.ps jhu.edu/~goodrich/pubs/point.ps.gz Cached: PS.gz PS PDF DjVu Image Update Help From: jhu.edu/~goodrich/pubs/ (more) From: jhu.edu/~goodrich/pubs/index Homepages: M.Goodrich [2] [3] R.Tamassia HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: This paper describes new methods for maintaining a point-location data structure for a dynamically-changing monotone subdivision S. The main approach is based on the maintenance of two interlaced spanning trees, one for S and one for the graphtheoretic planar dual of S. Queries are answered by using a centroid decomposition of the dual tree to drive searches in the primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan, leading to a scheme that achieves... (Update)
Context of citations to this paper: More
...not aware of an eOEcient planar point location structure that uses only the topology of the planar map. However, Goodrich and Tamassia [6] present a method for dynamic planar point location and a dynamic data structure which maintains a dynamically changing monotone subdivi...
.... (P ) instead of P (as F (V (P ) F (P ) We thus achieve the same performance as Goodrich and Tamassia s 3 d point location structure [19]. 16 4. Some practical issues. With no additional work, Hull4( can return the incidence structure between facets and ridges; this fact...
Cited by: More
Range Searching and Point Location among Fat Objects - Overmars, van der Stappen (1994) (Correct)
Two- and Three-Dimensional Point Location in.. - de Berg, van Kreveld, .. (1991) (Correct)
Primal Dividing and Dual Pruning: Output-Sensitive.. - Chan, Snoeyink, Yap (1997) (Correct)
Active bibliography (related documents): More All
0.6: Dynamic and I/O-Efficient Algorithms for Computational Geometry.. - Chiang (1995) (Correct)
0.5: Dynamization of the Trapezoid Method for Planar Point.. - Chiang, Tamassia (1992) (Correct)
0.5: A Unified Approach to Dynamic Point Location, Ray.. - Chiang, Preparata.. (1992) (Correct)
Similar documents based on text: More All
0.4: I/O-Efficient Dynamic Planar Point Location - Arge, Vahrenhold (Correct)
0.3: An Efficient Dynamic and Distributed Cryptographic.. - Goodrich, Tamassia, Hasic (2002) (Correct)
0.2: Biased Finger Trees and Three-Dimensional Layers of Maxima - Atallah, Goodrich, al. (1994) (Correct)
Related documents from co-citation: More All
18: Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
17: Optimal point location in a monotone subdivision (context) - Edelsbrunner, Guibas et al. - 1986
16: Planar point location using persistent search trees (context) - Sarnak, Tarjan - 1986
BibTeX entry: (Update)
M. Goodrich and R. Tamassia. Dynamic trees and dynamic point location. In Proc. 23rd Annu. ACM Sympos. Theory Comput., pages 523--533, 1991. http://citeseer.nj.nec.com/goodrich91dynamic.html More
@inproceedings{ goodrich91dynamic,
author = "Michael T. Goodrich and Roberto Tamassia",
title = "Dynamic trees and dynamic point location",
pages = "523--533",
year = "1991",
url = "citeseer.nj.nec.com/goodrich91dynamic.html" }
Citations (may not include all citations):1102 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
459 Graph Theory with Applications (context) - Bondy, Murty - 1976
219 Primitives for the manipulation of general subdivisions and .. (context) - Guibas, Stolfi - 1985
154 A data structure for dynamic trees (context) - Sleator, Tarjan - 1983
134 Optimal search in planar subdivisions (context) - Kirkpatrick - 1983
102 Planar point location using persistent search trees (context) - Sarnak, Tarjan - 1986
100 Optimal point location in a monotone subdivision (context) - Edelsbrunner, Guibas et al. - 1986
100 Making data structures persistent (context) - Driscoll, Sarnak et al. - 1989
96 Priority search trees (context) - McCreight - 1985
96 Linear-time algorithms for linear programming in R 3 and rel.. (context) - Megiddo - 1983
77 Lineartime algorithms for visibility and shortest path probl.. (context) - Guibas, Hershberger et al. - 1987
76 The design of dynamic data structures (context) - Overmars - 1983
61 A data structuring technique (context) - Chazelle, Guibas et al. - 1986
56 Dynamic algorithms in computational geometry - Chiang, Tamassia - 1992
44 Maintenance of a minimum spanning forest in a dynamic planar.. - Eppstein, Italiano et al. - 1992
44 Location of a point in a planar subdivision and its applicat.. (context) - Lee, Preparata - 1977
42 A theorem on polygon cutting with applications (context) - Chazelle - 1982
41 of EATCS Monographs on Theoretical Computer Science (context) - Edelsbrunner, Combinatorial et al. - 1987
37 of Data Structures and Algorithms (context) - Mehlhorn, Searching - 1984
35 Adding range restriction capability to dynamic data structur.. (context) - Willard, Lueker - 1985
33 Fully dynamic point location in a monotone subdivision (context) - Preparata, Tamassia - 1989
30 Searching and storing similar lists (context) - Cole - 1986
27 Dynamic point location in general subdivisions (context) - Baumgarten, Jung et al. - 1994
26 A new approach to planar point location (context) - Preparata - 1981
25 Dynamic ray shooting and shortest paths via balanced geodesi.. (context) - Goodrich, Tamassia - 1993
24 Triangulating a simple polygon (context) - Garey, Johnson et al. - 1978
22 New results on dynamic planar point location (context) - Cheng, Janardan - 1992
19 An optimal worst case algorithm for reporting intersections .. (context) - Bentley, Wood - 1980
16 A unified approach to dynamic point location (context) - Chiang, Preparata et al. - 1993
10 A balanced search tree with O (context) - Levcopoulos, Overmars - 1988
8 Parallel techniques for computational geometry (context) - Atallah - 1992
8 Dynamization of geometric data structures (context) - Fries, Mehlhorn et al. - 1985
6 Biased finger trees and threedimensional layers of maxima - Atallah, Goodrich et al. - 1994
6 Zerlegung einer planaren Unterteilung der Ebene und ihre Anw.. (context) - Fries - 1985
3 Computational geometry (context) - O'Rourke - 1988
2 Discrete Comput (context) - polygon, time - 1991
1 Discrete Comput (context) - intersection, plane - 1989
1 IEEE Trans (context) - geometry, survey - 1984
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.cs.jhu.edu/~goodrich/pubs/): More
On the Complexity of Optimization Problems for 3-Dimensional.. - Das, Goodrich (1995) (Correct)
Snap Rounding Line Segments Efficiently in Two and.. - Goodrich, Guibas.. (1997) (Correct)
Bounded-Independence Derandomization of Geometric.. - Goodrich, Ramos (1996) (Correct)
Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback
CiteSeer - citeseer.org - Terms of Service - Privacy Policy - Copyright © 1997-2002 NEC Research Institute