Realistic input models for geometric algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Realistic input models for geometric algorithms

Full text

Pdf (1.41 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 294 - 303

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Mark de Berg	Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands
Matthew Katz	Departments of Industrial Engineering & Management and Mathematics & Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel
A. Frank van der Stappen	Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands
Jules Vleugels	Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 21, Citation Count: 26

Additional Information:

references cited by index terms 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/262839.262986 What is a DOI?

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	Pankaj K. Agarwal , Matthew J. Katz , Micha Sharir, Computing depth orders for fat objects and related problems, Computational Geometry: Theory and Applications, v.5 n.4, p.187-206, Nov. 1995 [doi>10.1016/0925-7721(95)00005-8]
	2	Pankaj K. Agarwal , Jirí Matousek, On Range Searching with Semialgebraic Sets, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.1-13, August 24-28, 1992
	3	H. Alt, R. Fleischer, M. Kauhnann, K. Mehlhorn, S. N/iher, S. Schirra, and C. Uhrig. Approximate motion planning and the complexity of the boundary of the union of simple geometric figures. Algorithmica, 8:391-406, 1992.
	4	B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986.
	5	Z. Chen and J. A. Guevara. System selection of very important points (VIP) from digital terrain models for constructing triangular irregular networks. In Proc. 8th Internat. Sympos. Comput.-Assist. Cartog. (Auto- Carto), pages 50-56, 1988.
	6	Mark de Berg, Linear Size Binary Space Partitions for Fat Objects, Proceedings of the Third Annual European Symposium on Algorithms, p.252-263, September 25-27, 1995
	7	R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett., 12(3):133-137, 1981.
	8	D. T. Lee and C. K. Wong. Voronoi diagrams in L t (L#o) metrics with 2-dimensional storage applications. SIAM J. Comput., 9:200-211, 1980.
	9	Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
	10	Joseph S. B. Mitchell , David M. Mount , Subhash Suri, Query-sensitive ray shooting, Proceedings of the tenth annual symposium on Computational geometry, p.359-368, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178094]
	11	Mark H. Overmars , A. Frank van der Stappen, Range searching and point location among fat objects, Journal of Algorithms, v.21 n.3, p.629-656, Nov. 1996 [doi>10.1006/jagm.1996.0063]
	12	Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
	13	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	14	Otfried Schwarzkopf , Jules Vleugels, Range searching in low-density environments, Information Processing Letters, v.60 n.3, p.121-127, Nov. 11, 1996 [doi>10.1016/S0020-0190(96)00154-8]
	15	A. F. van der Stappen. Motion Planning amidst Fat Obstacles. Ph.D. thesis, Dept. Comput. Sci., Utrecht Univ., Utrecht# the Netherl#ads, October 1994.
	16	A. F. van der Stappen and M. H. Overmars. Motion planning in environments with low obstacle density. Technical Report UU-CS-1995-33, Dept. Comput. Sci., Utrecht Univ., Utrecht, the Netherlands, October 1995.
	17	Marc J. van Kreveld, On Fat Partitioning, Fat Covering and the Union Size of Polygons (Extended Abstract), Proceedings of the Third Workshop on Algorithms and Data Structures, p.452-463, August 11-13, 1993
	18	Jules Vleugels. On Fatness and Fitness#Realistic Input Models for Geometric Algorithms. Ph.D. thesis, Dept. Comput. Sci., Utrecht Univ., Utrecht, the Netherlands, March 1997.

CITED BY 26

	Boris Aronov , Hervé Brönnimann , Allen Y. Chang , Yi-Jen Chiang, Cost prediction for ray shooting, Proceedings of the eighteenth annual symposium on Computational geometry, p.293-302, June 05-07, 2002, Barcelona, Spain
	Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain
	Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Journal of the ACM (JACM), v.46 n.6, p.833-857, Nov. 1999
	Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States
	Boris Aronov , Mark de Berg , A. Frank van der Stappen , Petr Švestka , Jules Vleugels, Motion planning for multiple robots, Proceedings of the fourteenth annual symposium on Computational geometry, p.374-382, June 07-10, 1998, Minneapolis, Minnesota, United States
	Pedro A. Ramos, Computing roundness is easy if the set is almost round, Proceedings of the fifteenth annual symposium on Computational geometry, p.307-315, June 13-16, 1999, Miami Beach, Florida, United States
	John Hershberger , Subhash Suri, Simplified kinetic connectivity for rectangles and hypercubes, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 07-09, 2001, Washington, D.C., United States
	Subhash Suri , Philip M. Hubbard , John F. Hughes, Analyzing bounding boxes for object intersection, ACM Transactions on Graphics (TOG), v.18 n.3, p.257-277, July 1999
	Tetsuo Asano , Mark de Berg , Otfried Cheong , Leonidas J. Guibas , Jack Snoeyink , Hisao Tamaki, Spanning trees crossing few barriers, Proceedings of the fifteenth annual symposium on Computational geometry, p.41-48, June 13-16, 1999, Miami Beach, Florida, United States
	Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.830-839, January 17-19, 1999, Baltimore, Maryland, United States
	Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.828-837, January 06-08, 2002, San Francisco, California
	Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
	Frédo Durand , George Drettakis , Claude Puech, The 3D visibility complex, ACM Transactions on Graphics (TOG), v.21 n.2, p.176-206, April 2002
	Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003
	Eti Ezra , Micha Sharir, Output-sensitive construction of the union of triangles, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Mark de Berg , Matthew J. Katz , Mark H. Overmars , A. Frank van der Stappen , Jules Vleugels, Models and motion planning, Computational Geometry: Theory and Applications, v.23 n.1, p.53-68, July 2002
	Jeff Erickson, Local polyhedra and geometric graphs, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Siu-Wing Cheng , Kam-Hing Lee, Quadtree, ray shooting and approximate minimum weight Steiner triangulation, Computational Geometry: Theory and Applications, v.23 n.2, p.99-116, September 2002
	Mirela Damian, Exact and approximation algorithms for computing optimal fat decompositions, Computational Geometry: Theory and Applications, v.28 n.1, p.19-27, May 2004
	Herman J. Haverkort , Mark de Berg , Joachim Gudmundsson, Box-trees for collision checking in industrial installations, Proceedings of the eighteenth annual symposium on Computational geometry, p.53-62, June 05-07, 2002, Barcelona, Spain
	B. Aronov , A. Efrat , V. Koltun , Micha Sharir, On the union of κ-round objects, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Steven P. Callahan , Milan Ikits , Joao L. D. Comba , Claudio T. Silva, Hardware-Assisted Visibility Sorting for Unstructured Volume Rendering, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.285-295, May 2005
	Jeff Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications, v.31 n.1-2, p.101-125, May 2005
	Mark de Berg , Micha Streppel, Approximate range searching using binary space partitions, Computational Geometry: Theory and Applications, v.33 n.3, p.139-151, February 2006
	Boris Aronov , Hervé Brönnimann , Allen Y. Chang , Yi-Jen Chiang, Cost prediction for ray shooting in octrees, Computational Geometry: Theory and Applications, v.34 n.3, p.159-181, July 2006
	Siddhartha Chaudhuri , Vladlen Koltun, Smoothed analysis of probabilistic roadmaps, Computational Geometry: Theory and Applications, v.42 n.8, p.731-747, October, 2009