Yi-Jen Chiang, Roberto Tamassia  Home/Search
Context Related
| poly.edu/chiang/cgsurvey.ps Cached: PS.gz PS PDF DjVu Image Update Help From: poly.edu/chiang/ (more) Homepages: Y.Chiang [2] [3] R.Tamassia HPSearch (Update Links) |
Rate this article:      (best)Comment on this article |
Abstract: Research on dynamic algorithms for geometric problems has received increasing attention in the last years, and is motivated by many important applications in circuit layout, computer graphics, and computer-aided design. In this paper we survey dynamic algorithms and data structures in the area of computational geometry. Our work has a twofold purpose: it introduces the area to the nonspecialist and reviews the state-of-the-art for the specialist. (Update)
Context of citations to this paper: More
...They can reduce the space usage to O(n) if the queries are also part of the off line information. In a survey paper Chiang and Tamassia [CT92] regard dynamic planar convex hull as one of the two most important problems in dynamic computational geometry. More precisely they...
...the range tree are both static and internal memory structures. To dynamize a static data structure some standard techniques can be used [12]. For example, the global rebuilding [24] or the logarithmic method [8] To externalize an internal memory data structure, a widely used...
Cited by: More
Semi-Online Maintenance of Geometric Optima and Measures - Chan (2003) (Correct)
On Dynamic Algorithms for Algebraic Problems - Reif, R. (1997) (Correct)
Aggregation Computation over Complex Objects - Zhang (2002) (Correct)
Active bibliography (related documents): More All
4.9: Efficient Splitting and Merging Algorithms for Order.. - Grossi, Italiano (1997) (Correct)
2.3: Dynamic Algorithms in Computational Geometry - Li (Correct)
2.2: Geometric Range Searching and Its Relatives - Agarwal, Erickson (1999) (Correct)
Similar documents based on text: More All
0.1: Dynamization of the Trapezoid Method for Planar Point.. - Chiang, Tamassia (1992) (Correct)
0.1: Dynamic and I/O-Efficient Algorithms for Computational Geometry.. - Chiang (1995) (Correct)
0.1: A Unified Approach to Dynamic Point Location, Ray.. - Chiang, Preparata.. (1992) (Correct)
Related documents from co-citation: More All
21: The Design of Dynamic Data Structures (context) - Overmars - 1983
20: Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
19: Multidimensional divide-and-conquer (context) - Bentley - 1980
BibTeX entry: (Update)
Y.-J. Chiang and R. Tamassia, "Dynamic Algorithms in Computational Geometry," Proceedings of IEEE, Special Issue on Computational Geometry 80(9) (1992), 362-- 381. http://citeseer.nj.nec.com/chiang92dynamic.html More
@techreport{ chiang91dynamic,
author = "Yi-Jen Chiang and Roberto Tamassia",
title = "Dynamic Algorithms in Computational Geometry",
number = "CS-91-24",
year = "1991",
url = "citeseer.nj.nec.com/chiang92dynamic.html" }
Citations (may not include all citations):2929 Introduction to Algorithms (context) - Cormen, Leiserson et al. - 1990
417 Algorithms in Combinatorial Geometry (context) - Edelsbrunner - 1987
411 Computational Geometry (context) - Shamos - 1978
411 Computational Geometry (context) - Preparata, Shamos - 1985
279 Multidimensional Binary Search Trees Used for Associative Se.. (context) - Bentley - 1975
219 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
217 Data Structures and Network Algorithms (context) - Tarjan - 1983
154 A Data Structure for Dynamic Trees (context) - Sleator, Tarjan - 1983
153 Triangulating a Simple Polygon in Linear Time (context) - Chazelle - 1990
134 Optimal Search in Planar Subdivisions (context) - Kirkpatrick - 1983
116 Maintenance of Configurations in the Plane (context) - Overmars, van Leeuwen - 1981
102 Planar Point Location Using Persistent Search Trees (context) - Sarnak, Tarjan - 1986
102 A Dichromatic Framework for Balanced Trees (context) - Guibas, Sedgewick - 1978
101 A Linear Time Algorithm for a Special Case of Disjoint Set U.. (context) - Gabow, Tarjan - 1985
100 Optimal Point Location in a Monotone Subdivision (context) - Edelsbrunner, Guibas et al. - 1986
96 Priority Search Trees (context) - McCreight - 1985
86 Linear Programming and Convex Hulls Made Easy (context) - Seidel - 1990
81 Multidimensional Divide-and-Conquer (context) - Bentley - 1980
76 The Design of Dynamic Data Structures (context) - Overmars - 1983
76 Data Structures and Algorithms 3: Multi-dimensional Searchin.. (context) - Mehlhorn - 1984
75 Data Structures and Algorithms 1: Sorting and Searching (context) - Mehlhorn - 1984
71 Fast Algorithms for Geometric Traveling Salesman Problems (context) - Bentley - 1990
71 Amortized Computational Complexity (context) - Tarjan - 1985
69 A Linear-time Algorithm for Computing the Voronoi Diagram of.. (context) - Aggarwal, Guibas et al. - 1989
69 The Cell Probe Complexity of Dynamic Data Structures (context) - Fredman, Saks - 1989
66 Efficient Partition Trees (context) - Matousek - 1991
49 Convex Hulls of Finite Sets of Points in Two and Three Dimen.. (context) - Preparata, Hong - 1977
49 Decomposable Searching Problems I: Static to Dynamic Transfo.. (context) - Bentley, Saxe - 1980
47 A Functional Approach to Data Structures and its Use in Mult.. (context) - Chazelle - 1988
47 Applications of Random Sampling to On-line Algorithms in Com.. - Boissonnat, Devillers et al.
47 Quasi-optimal Upper Bounds for Simplex Range Searching and N.. (context) - Chazelle, Sharir et al. - 1990
46 A New Data Structure for Representing Sorted Lists (context) - Huddleston, Mehlhorn - 1982
45 Randomized Search Trees (context) - Aragon, Seidel - 1989
44 Location of a Point in a Planar Subdivision and its Applicat.. (context) - Lee, Preparata - 1977
43 Optimal Shortest Path Queries in a Simple Polygon (context) - Guibas, Hershberger - 1987
42 Decomposable Searching Problems (context) - Bentley - 1979
41 Preserving Order in a Forest in less than Logarithmic Time a.. (context) - Boas - 1977
41 Preserving Order in a Forest in less than Logarithmic Time (context) - Boas - 1975
39 Dynamic fractional cascading (context) - Mehlhorn, Naher - 1990
39 Dynamic Trees and Dynamic Point Location - Goodrich, Tamassia - 1991
39 Applications of a Semi-Dynamic Convex Hull Algorithm (context) - Hershberger, Suri - 1990
35 Adding Range Restriction Capability to Dynamic Data Structur.. (context) - Willard, Lueker - 1985
34 Algorithms for Klee's Rectangle Problems (context) - Bentley - 1977
33 Fully Dynamic Point Location in a Monotone Subdivision (context) - Preparata, Tamassia - 1989
32 Applications of a New Space Partitioning Technique (context) - Agarwal, Sharir - 1991
32 A Data Structure for Orthogonal Range Queries (context) - Lueker - 1978
31 Stable Maintenance of Point-set Triangulations in Two Dimens.. (context) - Fortune - 1989
28 Binary Search Trees of Bounded Balance (context) - Nievergelt, Reingold - 1973
28 Drawing Dynamic Trees (context) - Moen - 1990
27 Dynamic Point Location in General Subdivisions (context) - Baumgarten, Jung et al. - 1992
26 A New Approach to Planar Point Location (context) - Preparata - 1981
25 Biased Search Trees (context) - Bent, Sleator et al. - 1985
23 Ray Shooting and Other Applications of Spanning Trees with L.. (context) - Agarwal - 1989
22 New Results on Dynamic Planar Point Location (context) - Cheng, Janardan - 1990
22 Hidden Surface Removal for Rectangles (context) - Bern - 1990
21 the Convex Layers of a Planar Set (context) - Chazelle - 1985
21 Computational Geometry (context) - Yao - 1990
20 Randomized Multidimensional Search Trees: Dynamic Sampling (context) - Mulmuley - 1991
20 Efficient Worst-case Data Structures for Range Searching (context) - Bentley, Mauer - 1980
19 Algorithms for Automatic Graph Drawing: An Annotated Bibliog.. (context) - Eades, Tamassia - 1989
19 Fractional Cascading: I. A Data Structuring Technique (context) - Chazelle, Guibas - 1986
19 Dynamic Expression Trees and their Applications (context) - Cohen, Tamassia - 1991
17 the Average Number of Rebalancing Operations in WeightBalanc.. (context) - Blum, Mehlhorn - 1980
16 Range Searching in a Set of Line Segments (context) - Overmars - 1985
16 A Lower Bound on the Complexity of Orthogonal Range Queries (context) - Fredman - 1981
16 A framework for dynamic graph drawing - Cohen, Di Battista et al. - 1992
16 Worst-case Analysis of Region and Partial Region Searches in.. (context) - Lee, Wong - 1977
15 Blasting through the Information Theoretic Barrier with Fusi.. (context) - Fredman, Willard - 1990
15 Improving Partial Rebuilding by Using Simple Balance Criteri.. - Andersson - 1989
15 New Techniques for some Dynamic Closest-Point and Farthest-P.. (context) - Supowit - 1990
14 Dynamic Orthogonal Segment Intersection Search (context) - Imai, Asano - 1987
14 An Optimal Real Time Algorithm for Planar Convex Hulls (context) - Preparata - 1979
14 On Levels in Arrangements and Voronoi Diagrams (context) - Mulmuley - 1991
14 Offline Maintenance of Planar Configurations (context) - Hershberger, Suri - 1991
13 A New Approach to Rectangle Intersections, Part II (context) - Edelsbrunner - 1983
13 A New Approach to Rectangle Intersections, Part (context) - Edelsbrunner - 1983
13 Worst-case Optimal Insertion and Deletion Methods for Decomp.. (context) - Overmars, van Leeuwen - 1981
13 Maintaining the Minimal Distance of a Point Set in Less Than.. (context) - Smid - 1991
13 Maintaining the Minimal Distance of a Point Set in Polylogar.. (context) - Smid - 1991
13 An Optimal Algorithm for the On-line Closest-Pair Problem - Schwarz, Smid et al. - 1992
12 Efficient Algorithms for Geometric Graph Search Problems (context) - Imai, Asano - 1986
12 Randomized Multidimensional Search Trees: Lazy Balancing and.. (context) - Mulmuley - 1991
12 Randomized Multidimensional Search Trees: Further Results in.. (context) - Mulmuley - 1991
12 Efficient Point Location in a Convex Spatial Cell Complex (context) - Preparata, Tamassia - 1992
11 The Ultimate Planar Convex Hull Algorithm (context) - Kirkpatrick, Seidel - 1986
11 Proving Relative Lower Bounds for Incremental Algorithms (context) - Berman, Paull et al. - 1990
11 Applications of the Fusion Tree Method to Computational Geom.. (context) - Willard - 1992
11 Computation of the Axial View of a Set of Isothetic Parallel.. (context) - Preparata, Vitter et al. - 1990
10 On Maintaining the Width and Diameter of a Planar Point-set .. (context) - Janardan - 1991
10 Output-Sensitive Generation of the Perspective View of Isoth.. (context) - Preparata, Vitter et al. - 1989
10 New Data Structures for Orthogonal Range Queries (context) - Willard - 1985
10 Algorithms for Ray-shooting and Intersection Searching (context) - Cheng, Janardan - 1991
10 A Simplified Technique for Hidden-Line Elimination in Terrai.. - Preparata, Vitter - 1992
9 An Incremental Reconstruction Method for Dynamic Planar Poin.. (context) - Tamassia - 1991
9 Rectilinear Line Segment Intersection, Layered Segment Trees.. (context) - Vaishnavi, Wood - 1982
9 Maintaining Range Trees in Secondary Memory, Part I: Partiti.. - Overmars, Smid et al. - 1990
8 Dynamization of Geometric Data Structures (context) - Fries, Mehlhorn et al. - 1985
8 Dynamic Planar Point Location with Optimal Query Time (context) - Preparata, Tamassia - 1990
8 Optimal Dynamization of Decomposable Searching Problems (context) - Mehlhorn, Overmars - 1981
8 Dynamization of Decomposable Searching Problems Yielding Goo.. (context) - Overmars, van Leeuwen - 1981
8 Dynamization of Decomposable Searching Problems (context) - van Leeuwen, Wood - 1980
8 General Methods for Adding Range Restrictions to Decomposabl.. (context) - Scholten, Overmars - 1989
7 Planar Geometric Location Problems and Maintaining the Width.. (context) - Agarwal, Sharir - 1991
7 Dynamic Location in an Arrangement of Line Segments in the P.. (context) - Devillers, Teillaud et al. - 1992
7 Dynamization of the Trapezoid Method for Planar Point Locati.. - Chiang, Tamassia - 1991
7 Deferred Data Structuring (context) - Karp, Motwani et al. - 1988
7 A Data Structure for Dynamic Range Queries (context) - Lueker, Willard - 1982
7 K-d Trees for Semidynamic Point Sets (context) - Bentley - 1990
7 Rectangular Point Location in d Dimensions with Applications (context) - Edelsbrunner, Haring et al. - 1986
7 The Inherent Complexity of Dynamic Data Structures Which Acc.. (context) - Fredman - 1980
6 the Application of Sheared Retrieval to Orthogonal Range Que.. (context) - Willard - 1986
6 More on cutting arrangements and spanning trees with low cro.. (context) - Matousek - 1990
6 Dynamic Data Structures on Multiple Storage Media (context) - Smid - 1989
6 Dynamic Point Location in Arrangements of Hyperplanes (context) - Mulmuley, Sen - 1991
5 Analysis of KDT-Trees: KD-Trees Improved by Local Reorganiza.. (context) - Cunto, Lau et al. - 1989
5 Lower Bounds for the Addition-Subtraction Operations in Orth.. (context) - Willard - 1989
5 Hysterical B-Trees (context) - Maier, Salveter - 1981
5 Data Structures for Retrieval on Square Grids (context) - Katz, Volper - 1986
5 A Unified Approach to Dynamic Point Location, Ray Shooting a.. - Chiang, Preparata et al. - 1992
5 Efficient Dynamic Algorithms for Some Geometric Intersection.. (context) - Cheng, Janardan - 1990
4 Fractional Cascading: II. Applications (context) - Chazelle, Guibas - 1986
4 Dynamic Output-Sensitive Hidden Surface Removal for c-Orient.. (context) - de Berg - 1991
4 Applying Parallel Processing Techniques to Classification Pr.. (context) - Goodrich - 1990
4 Range Trees with Slack Parameter (context) - Smid - 1991
4 Maintaining Range Trees in Secondary Memory, Part II: Lower .. (context) - Smid, Overmars - 1990
4 A Dynamic Fixed Windowing Problem (context) - Klein, Nurmi et al. - 1989
4 Dynamically Computing the Maxima of Decomposable Functions, .. (context) - Dobkin, Suri - 1989
4 Finding a Manhattan Path and Related Problems (context) - Lipski - 1983
3 Shallow Interdistance Selection and Interdistance Enumeratio.. (context) - Salowe - 1991
3 A New Approach to the Dynamic Maintenance of Maximal Points .. (context) - Frederickson, Rodger - 1990
3 Multidimensional Data Structures: Review and Outlook (context) - Iyengar, Kashyap et al. - 1988
3 An Information Organization Algorithm (context) - Adel'son-Vel'skii, Landis - 1962
3 the Dynamic Maintenance of Maximal Points in the Plane (context) - Janardan - 1991
3 Quasi-optimal range searching in space with finite VC-dimens.. (context) - Chazelle, Welzl - 1989
3 Concatenable Structures for Decomposable Problems (context) - van Kreveld, Overmars - 1989
3 Dynamic Solutions of Decomposable Searching Problems (context) - Maurer, Ottmann - 1979
3 Computing Point Enclosures (context) - Vaishnavi - 1982
3 Multidimensional Balanced Binary Trees (context) - Vaishnavi - 1989
3 Updating a Balanced Search Tree in O(1) Rotations (context) - Tarjan - 1983
3 Efficient Search Trees (context) - Andersson - 1990
3 Dynamization of Order Decomposable Set Problems (context) - Overmars - 1981
2 A Worst-case Algorithm for Semi-online Updates on Decomposab.. (context) - Smid - 1990
2 Some Principles for Dynamizing Decomposable Searching Proble.. (context) - Overmars, van Leeuwen - 1981
2 Divided K-D Trees - van Kreveld, Overmars - 1988
2 Optimizing the Dynamization of Decomposable Searching Proble.. (context) - Edelsbrunner - 1979
2 The Art of Dynamizing (context) - van Leeuwen, Overmars - 1981
2 Two General Method for Dynamizing Decomposable Searching Pro.. (context) - Overmars, van Leeuwen - 1981
2 Dynamic Systems of Static Data Structures (context) - van Leeuwen, Maurer - 1980
2 the Dynamization of Data Structures (context) - Rao, Vaishnavi et al. - 1988
2 Exploiting Linear Merging and Extra Storage in the Maintenan.. (context) - Gowda, Kirkpatrick - 1980
2 An O(n log n) Manhattan Path Algorithm (context) - Lipski - 1984
2 Dynamic Weighted Data Structures (context) - Bent - 1982
2 Dynamic Voronoi Diagrams (context) - Gowda, Kirkpatrick et al. - 1983
2 Enumerating k distances for n points in the plane (context) - Dickerson, Drysdale - 1991
2 Efficient Spatial Point Location (context) - Preparata, Tamassia - 1989
1 Randomized Incremental Construction of Delauney and Voronoi .. (context) - Guibas, Knuth et al. - 1990
1 Suchen in dynamischen planaren Unterteilungen (context) - Fries - 1990
1 Multidimensional Search Trees That Provide New Types of Meme.. (context) - Willard - 1987
1 The Super-B-Tree Algorithm (context) - Willard - 1979
1 Multidimensional (a, b)-Trees: An Efficient Dynamic Multidim.. (context) - Vaishnavi - 1990
1 Dynamic Rectangular Point Location, with an Application to t.. (context) - Smid - 1991
1 A Problem in Multivariate Statistics: Algorithms, Data Struc.. (context) - Bentley, Shamos - 1977
1 On k-dimensional Balanced Binary Trees (context) - Vaishnavi - 1990
1 private communication (context) - Smid
1 Robust Balancing in B-Trees (context) - Huddleston, Mehlhorn - 1981
1 An O(n log n log log n) Algorithm for the On-line Closest Pa.. (context) - Schwarz, Smid - 1992
1 Line Convex Hull Algorithm on Reals (context) - Franciosa, Talamo et al. - 1990
1 Lower Bounds for Orthogonal Range Search II. The Arithmetic .. (context) - Chazelle - 1990
1 Dynamic Partition Trees - Schipper, Overmars - 1990
1 Persistence, Amortization and Randomization (context) - Dietz, Raman - 1991
1 Efficient Maintenance of the Union of Intervals on a Line, w.. (context) - Cheng, Janardan - 1991
1 A Simple Online Randomized Incremental Algorithm for Computi.. (context) - Aurenhammer, Schwarzkopf - 1991
1 Dynamic Deferred Data Structuring (context) - Ching, Mehlhorn et al. - 1990
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://cis.poly.edu/chiang/): More
I/O Optimal Isosurface Extraction (Extended Abstract) - Chiang, Silva (Correct)
On the Maximum Scatter TSP (Extended Abstract) - Arkin, al. (1997) (Correct)
Optimal Shortest Path and Minimum-Link Path Queries Between.. - Chiang, Tamassia (1994) (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