Planar point location using persistent search trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Planar point location using persistent search trees

Full text

Pdf (1.22 MB)

Source

Communications of the ACM archive
Volume 29 , Issue 7 (July 1986) table of contents

Pages: 669 - 679

Year of Publication: 1986

ISSN:0001-0782

Authors

Neil Sarnak	IBM T. J. Watson Research Center, Yorktown Heights, NY
Robert E. Tarjan	Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 143, Citation Count: 90

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/6138.6151 What is a DOI?

ABSTRACT

A classical problem in computational geometry is the planar point location problem. This problem calls for preprocessing a polygonal subdivision of the plane defined by n line segments so that, given a sequence of points, the polygon containing each point can be determined quickly on-line. Several ways of solving this problem in O(log n) query time and O(n) space are known, but they are all rather complicated. We propose a simple O(log n)-query-time, O(n)-space solution, using persistent search trees. A persistent search tree differs from an ordinary search tree in that after an insertion or deletion, the old version of the tree can still be accessed. We develop a persistent form of binary search tree that supports insertions and deletions in the present and queries in the past. The time per query or update is O(log m), where m is the total number of updates, and the space needed is O(1) per update. Our planar point location algorithm is an immediate application of this data structure. The structure also provides an alternative to Chazelle's "hive graph" structure, which has a variety of applications in geometric retrieval.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ad&on-Velikii. GM. and Landis. E.M. An algorithm for the organization of information. Souief Math. Dokl. 3, 5 (Sept. 1962). 1259-1262.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Bayer, R. Symmetric binary B-trees: Data structure and maintenance algorithms. Acfa Inform. 1.4 (Nov. 1972), 290-306.
	4	Bentley, J.L.. and Saxe, J.B. Decomposable searching problems I: Static-to-dynamic transformation. J AIgorifhms I. 4 (Dec. 1980). 301-358.
	5	Blum, N.. and Mehlhorn. K. On the average number of rebalancing operations in weight-balanced trees. A-78/06. Fachbereich Angewandte Mathematik und Informatik. UniversitBt des Saarlandes. Saarbrdcken. West Germany, 1978.
	6	Brown, M.R., and Tarjan, R.E. Design and analysis of data structures for representing sorted lists. SIAM /. Comput. 9, 3 (Aug. 1980), 594-614.
	7	Chazelle. B. Filtering search: A new approach to query-answering. In Proceedings of 24fh Annual IEEE Symposium on Foundations of Computer Sc~e&. (Tucson. Ariz.. Nov. 7-9. 1983). 122-132.
	8	Chazelle. B. How to search in history. Inform. Control. to appear.
	9	Bernard Chazelle , Leonidas J. Guibas, Fractional Cascading: A Data Structuring Technique with Geometric Applications, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.90-100, July 15-19, 1985
	10	Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
	11	Dobkin. D., and Lipton. R.J. Multidimensional search problems. SIAM J. Compuf. 5, 2 (June 1976). 181-186.
	12	Dobkin. D.P., and Munro, J.I. Efficient uses of the past. In Proceedings of 2lsf A~rwal IEEE Symposium ou Foundafions of Computer Science, (Syracuse. N.Y., Oct. 13-16. 1980), 200-206.
	13	Edelsbrunner. H., Guibas. L.J.. and Stolfi, J. Optimal point location in a monotone subdivision. Rep. 2, Digital Systems Research Center, Palo Alto, Calif.. 1984.
	14	Guibas. L.J.. and Sedgewick. R. A dichromatic framework for balanced trees. In Proceedings of 19th Annual IEEE Symposium on Foundarions of Compufer Science, (Ann Arbor, Mich.. Oct. 16-18. 1978), 8-21.
	15	Scott Huddleston , Kurt Mehlhorn, Robust Balancing in B-Trees, Proceedings of the 5th GI-Conference on Theoretical Computer Science, p.234-244, March 23-25, 1981
	16	Huddleston. S.. and Mehlhorn. K. A new data structure for representing sorted lists. Acta Inform. 17, 2 (June 1982), 157-184.
	17	Huddleston, S. An efficient scheme for fast local updates in linear lists. Department of Information and Computer Science, Univ. of California, Irvine. 1981.
	18	Kirkpatrick, D. Optimal search in planar subdivisions. SIAM \. Compuf. 12. 1 (Feb. 1983). 28-35.
	19	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	20	S. Rao Kosaraju, Localized search in sorted lists, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.62-69, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802458]
	21	Krijnen. T.. and Me&ens, L.G.L.T. Making B-trees work for B. IW 219/83. The Mathematical Centre. Amsterdam, The Netherlands, 1983.
	22	Lee, D.T., and Preparata. F.P. Location of a point in a planar subdivision and its appiications. SlAM /. CompuL 6. 3 (Sept. 1977), 594-606.
	23	Lipton, R.J.. and Tarjan. R.E. Applications of a planar separator theorem. In Proceedings of 18th Annual 1EEE Symposium on Foundations of Compukr Science, (Providence, R.I., Oct. Il-Nov. 2, 1977). 162-170.
	24	Lipton, R.J., and Tarjan, R.E. A separator theorem for planar graphs. SlAM /. Appl. Math. 36, 2 (Apr. 19791, 177-189.
	25	Maier, D.. and Salveter, S.C. Hysterical B-trees. Inform. Process. Letf. 12.4 (Aug. 13. 1981). 199-202.
	26	Mehlhorn. K. Data Sfrucfures and Algorifhms I: Sorting and Searching. Springer-Verlag. Berlin. 1984.
	27	Myers, E. W. AVL dags. Tech. Rep. 82-9, Department of Computer Science. Univ. of Arizona. Tucson. Ariz.. 1982.
	28	Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
	29	Nievergelt. J.. and Reingold. E.M. Binary search trees of bounded balance. SIAM 1. Compuf. 2. 1 (Mar. 1973), 33-43.
	30	Olivib. H. A new class of balanced search trees: Half-balanced binary search trees. RAIRO lnformalique ThPorefique. 16 (1982). 51-71.
	31	Overman. M.H. Searching in the past 1. Inform. Confrol. to appear.
	32	Preparata. F.P. A new approach to planar point location. SIAM /. Comput IO. 3 (Aug. 1981). 473-482.
	33	Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
	34	Neil Ivor Sarnak, Persistent data structures, 1986
	35	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	36	Swart, G. Efficient algorithms for computing geometric intersections. Tech. Rep. #85-01-02. Department of Computer Science. Univ. of Washington, Seattle, 1985.
	37	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	38	Tarjan, R.E. Updating a balanced search tree in O(1) rotations. lnform. Process. Left. 16, 5 (June 1983), 2.53-257.
	39	Tarjan. R.E. Amortized computational complexity. SIAM}. Alg. Disc. Mefh. 6. 2 (Apr. 1985). 306-318.
	40	R E Tarjan , C J Van Wyk, A linear-time algorithm for triangulating simple polygons, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.380-388, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12170]
	41	Athanasios K. Tsakalidis, AVL-Trees for Localized Search, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.473-485, July 16-20, 1984

CITED BY 90

	Sunil Arya , Theocharis Malamatos , David M. Mount, Entropy-preserving cuttings and space-efficient planar point location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.256-261, January 07-09, 2001, Washington, D.C., United States
	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States
	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Linear-time triangulation of a simple polygon made easier via randomization, Proceedings of the sixteenth annual symposium on Computational geometry, p.201-212, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Hervé Brönnimann, Degenerate convex hulls on-line in any fixed dimension, Proceedings of the fourteenth annual symposium on Computational geometry, p.249-258, June 07-10, 1998, Minneapolis, Minnesota, United States
	Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
	Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.191-200, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	David Lomet , Betty Salzberg, Access methods for multiversion data, ACM SIGMOD Record, v.18 n.2, p.315-324, June 1989
	Haim Kaplan , Robert E. Tarjan, Persistent lists with catenation via recursive slow-down, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.93-102, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991
	Paul F. Dietz , Rajeev Raman, Persistence, amortization and randomization, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.78-88, January 28-30, 1991, San Francisco, California, United States
	Sunil Arya , Theocharis Malamatos , David M. Mount, A simple entropy-based algorithm for planar point location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.262-268, January 07-09, 2001, Washington, D.C., United States
	Amir M. Ben-Amram , Zvi Galil, On pointers versus addresses, Journal of the ACM (JACM), v.39 n.3, p.617-648, July 1992
	Yi-Jen Chiang , Roberto Tamassia, Dynamization of the trapezoid method for planar point location (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.61-70, June 10-12, 1991, North Conway, New Hampshire, United States
	Udo Adamy , Raimund Seidel, On the exact worst case query complexity of planar point location, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 25-27, 1998, San Francisco, California, United States
	Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States
	Qingbo Zhu , Windsor W. Hsu, Fossilized index: the linchpin of trustworthy non-alterable electronic records, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	David Bruce, The treatment of state in optimistic systems, ACM SIGSIM Simulation Digest, v.25 n.1, p.40-49, July 1995
	Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
	Ketan Mulmuley , Sandeep Sen, Dynamic point location in arrangements of hyperplanes, Proceedings of the seventh annual symposium on Computational geometry, p.132-141, June 10-12, 1991, North Conway, New Hampshire, United States
	Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.44-53, January 25-27, 1993, Austin, Texas, United States
	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States
	Otto Nurmi , Eljas Soisalon-Soininen, Uncoupling updating and rebalancing in chromatic binary search trees, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.192-198, May 29-31, 1991, Denver, Colorado, United States
	M. K. Zand , H. Farhat , H. Saiedian, Persistent structures to store moving images, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.21-27, April 1992, Kansas City, Missouri, United States
	Pankaj K. Agarwal , Lars Arge , Gerth Stølting Brodal , Jeffrey S. Vitter, I/O-efficient dynamic point location in monotone planar subdivisions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.11-20, January 17-19, 1999, Baltimore, Maryland, United States
	Kurt W. Deschler , Elke A. Rundensteiner, B+ retake: sustaining high volume inserts into large data pages, Proceedings of the 4th ACM international workshop on Data warehousing and OLAP, p.56-63, November 09-09, 2001, Atlanta, Georgia, USA
	G. Wilfong, Motion planning in the presence of movable obstacles, Proceedings of the fourth annual symposium on Computational geometry, p.279-288, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Timothy M. Chan, Deterministic algorithms for 2-d convex programming and 3-d online linear programming, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.464-472, January 05-07, 1997, New Orleans, Louisiana, United States
	Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.537-546, January 07-09, 2001, Washington, D.C., United States
	Curtis P. Kolovson , Michael Stonebraker, Segment indexes: dynamic indexing techniques for multi-dimensional interval data, ACM SIGMOD Record, v.20 n.2, p.138-147, June 1991
	Haim Kaplan , Robert E. Tarjan, Purely functional representations of catenable sorted lists, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.202-211, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Nicholas Pippenger, Pure versus impure Lisp, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.104-109, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Pankaj K. Agarwal , Lars Arge , T. M. Murali , Kasturi R. Varadarajan , Jeffrey Scott Vitter, I/O-efficient algorithms for contour-line extraction and planar graph blocking, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.117-126, January 25-27, 1998, San Francisco, California, United States
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	K. Mulmuley, A fast planar partition algorithm, II, Proceedings of the fifth annual symposium on Computational geometry, p.33-43, June 05-07, 1989, Saarbruchen, West Germany
	Kim S. Larsen, Relaxed multi-way trees with group updates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.93-101, May 2001, Santa Barbara, California, United States
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States
	P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany
	Giuseppe Liotta , France P. Preparata , Roberto Tamassia, Robust proximity queries: an illustration of degree-driven algorithm design, Proceedings of the thirteenth annual symposium on Computational geometry, p.156-165, June 04-06, 1997, Nice, France
	Binay K. Bhattacharya , Gautam Das , Asish Mukhopadhyay , Giri Narasimhan, Optimally computing a shortest weakly visible line segment inside a simple polygon, Computational Geometry: Theory and Applications, v.23 n.1, p.1-29, July 2002
	Gautam Das , Giri Narasimhan, Optimal linear-time algorithm for the shortest illuminating line segment in a polygon, Proceedings of the tenth annual symposium on Computational geometry, p.259-266, June 06-08, 1994, Stony Brook, New York, United States
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Marco Pellegrini, On point location and motion planning among simplices, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.95-104, May 23-25, 1994, Montreal, Quebec, Canada
	M. Bern, Hidden surface removal for rectangles, Proceedings of the fourth annual symposium on Computational geometry, p.183-192, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Hanan Samet, Hierarchical representations of collections of small rectangles, ACM Computing Surveys (CSUR), v.20 n.4, p.271-309, Dec. 1988
	Mikhail J. Atallah , Michael T. Goodrich , Kumar Ramaiyer, Biased finger trees and three-dimensional layers of maxima: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.150-159, June 06-08, 1994, Stony Brook, New York, United States
	Ziv Gigus , John Canny , Raimund Seidel, Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.6, p.542-551, June 1991
	Gerth Stølting Brodal, Partially persistent data structures of bounded degree with constant update time, Nordic Journal of Computing, v.3 n.3, p.238-255, Fall 1996
	Pankaj K. Agarwal , Mark de Berg , Sariel Har-Peled , Mark H. Overmars , Micha Sharir , Jan Vahrenhold, Reporting intersecting pairs of convex polytopes in two and three dimensions, Computational Geometry: Theory and Applications, v.23 n.2, p.195-207, September 2002
	John Iacono , Stefan Langerman, Proximate planar point location, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Prosenjit Bose , Anna Lubiw , J. Ian Munro, Efficient visibility queries in simple polygons, Computational Geometry: Theory and Applications, v.23 n.3, p.313-335, November 2002
	Kim S. Larsen, Relaxed multi-way trees with group updates, Journal of Computer and System Sciences, v.66 n.4, p.657-670, 1 June 2003
	Eljas Soisalon-Soininen , Peter Widmayer, Single and bulk updates in stratified trees: an amortized and worst-case analysis, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	Richard Bird , Ralf Hinze, Functional Pearl trouble shared is trouble halved, Proceedings of the 2003 ACM SIGPLAN workshop on Haskell, p.1-6, August 28-28, 2003, Uppsala, Sweden
	Lars Arge , Andrew Danner , Sha-Mayn Teh, I/O-efficient point location using persistent B-trees, Journal of Experimental Algorithmics (JEA), 8, 2003
	M. Samadzadeh , W. Wichaipanitch, An interactive debugging tool for C based on dynamic slicing and dicing, Proceedings of the 1993 ACM conference on Computer science, p.30-37, February 16-18, 1993, Indianapolis, Indiana, United States
	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	B. Aronov , M. Sharir, Triangles in space or building (and analyzing) castles in the Air, Proceedings of the fourth annual symposium on Computational geometry, p.381-391, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	H. Edelsbrunner , L. J. Guibas , J. Hershberger , R. Seidel , M. Sharir, Implicitly representing arrangements of lines or segments, Proceedings of the fourth annual symposium on Computational geometry, p.56-69, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Haim Kaplan , Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM (JACM), v.46 n.5, p.577-603, Sept. 1999
	Jan Vahrenhold , Klaus H. Hinrichs, Planar point location for large data sets: to seek or not to seek, Journal of Experimental Algorithmics (JEA), 7, p.8, 2002
	Christian Ronse, A Bibliography on Digital and Computational Convexity (1961-1988), IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.2, p.181-190, February 1989
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Lars Arge , Jan Vahrenhold, I/O-efficient dynamic planar point location, Computational Geometry: Theory and Applications, v.29 n.2, p.147-162, October 2004
	Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Serban D. Porumbescu , Brian Budge , Louis Feng , Kenneth I. Joy, Shell maps, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	Alireza Zarei , Mohammad Ghodsi, Efficient computation of query point visibility in polygons with holes, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Journal of Algorithms, v.48 n.1, p.16-58, August 2003
	Alireza Zarei , Mohammad Ghodsi, Query point visibility computation in polygons with holes, Computational Geometry: Theory and Applications, v.39 n.2, p.78-90, February, 2008
	Tamas Abraham , John F. Roddick, Survey of Spatio-Temporal Databases, Geoinformatica, v.3 n.1, p.61-99, March 1999
	George Lagogiannis , Yannis Panagis , Spyros Sioutas , Athanasios Tsakalidis, A survey of persistent data structures, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
	David W. Krumme , Eynat Rafalin , Diane L. Souvaine , Csaba D. Tóth, Tight bounds for connecting sites across barriers, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Kurt Mehlhorn , Stefan Näher , Thomas Schilz , Stefan Schirra , Michael Seel , Raimund Seidel , Christian Uhrig, Checking geometric programs or verification of geometric structures, Proceedings of the twelfth annual symposium on Computational geometry, p.159-165, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proceedings of the fifth annual symposium on Computational geometry, p.315-325, June 05-07, 1989, Saarbruchen, West Germany
	Danny Krizanc , Pat Morin , Michiel Smid, Range mode and range median queries on lists and trees, Nordic Journal of Computing, v.12 n.1, p.1-17, March 2005
	Manuel Abellanas , Mercè Claverol , Ferran Hurtado, Point set stratification and Delaunay depth, Computational Statistics & Data Analysis, v.51 n.5, p.2513-2530, February, 2007
	Farshad Rostamabadi , Mohammad Ghodsi, Label updating to avoid point-shaped obstacles in fixed model, Theoretical Computer Science, v.369 n.1, p.197-210, 15 December 2006
	David Eppstein , Michael T. Goodrich , Nodari Sitchinava, Guard placement for efficient point-in-polygon proofs, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, ACM Transactions on Algorithms (TALG), v.3 n.2, p.13-es, May 2007
	Sunil Arya , Theocharis Malamatos , David M. Mount, A simple entropy-based algorithm for planar point location, ACM Transactions on Algorithms (TALG), v.3 n.2, p.17-es, May 2007
	Qingmin Shi , Joseph JaJa, Isosurface Extraction and Spatial Filtering using Persistent Octree (POT), IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.1283-1290, September 2006
	Rodrigo I. Silveira , Marc van Kreveld, Towards a definition of higher order constrained Delaunay triangulations, Computational Geometry: Theory and Applications, v.42 n.4, p.322-337, May, 2009
	Lars Arge , Gerth Stølting Brodal , S. Srinivasa Rao, External memory planar point location with logarithmic updates, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Sébastien Collette , Vida Dujmović , John Iacono , Stefan Langerman , Pat Morin, Distribution-sensitive point location in convex subdivisions, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.912-921, January 20-22, 2008, San Francisco, California
	Timothy M. Chan , Eric Y. Chen, In-place 2-d nearest neighbor search, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.904-911, January 20-22, 2008, San Francisco, California
	Noga Alon , Dan Halperin , Oren Nechushtan , Micha Sharir, The complexity of the outer face in arrangements of random segments, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Jean Cardinal , Sébastien Collette , Ferran Hurtado , Stefan Langerman , Belén Palop, Optimal location of transportation devices, Computational Geometry: Theory and Applications, v.41 n.3, p.219-229, November, 2008
	Prosenjit Bose , Eric Y. Chen , Meng He , Anil Maheshwari , Pat Morin, Succinct geometric indexes supporting point location queries, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.635-644, January 04-06, 2009, New York, New York
	Sang Won Bae , Kyung-Yong Chwa, The geodesic farthest-site Voronoi diagram in a polygonal domain with holes, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Timothy M. Chan , Eric Y. Chen, Optimal in-place algorithms for 3-D convex hulls and 2-D segment intersection, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark

INDEX TERMS

Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Geometrical problems and computations; Computations on discrete structures

General Terms:
Algorithms, Theory

REVIEW

"Frans J. Peters : Reviewer"

As the authors state in their Abstract, the planar point location problem is a classical problem in computational geometry. Several ways of solving this problem in O(log n) query time and O(n) space ar more...

Collaborative Colleagues:

Neil Sarnak: colleagues

Robert E. Tarjan: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player