Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations

Full text

Pdf (1.05 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 274 - 283

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Ernst P. Mücke	Los Alamos National Laboratory, Los Alamos, New Mexico, ANSYS, Inc., 201 Johnson Road, Houston, PA
Isaac Saias	Los Alamos National Laboratory, Los Alamos, New Mexico, M.S. K987, Los Alamos, NM
Binhai Zhu	Los Alamos National Laboratory, Los Alamos, New Mexico, M.S. K987, Los Alamos, NM

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): 39, Citation Count: 10

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/237218.237396 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.

	AEI+85	T. Asano, M. Edahiro, H. Imai, M. Iri, and K. Murota. Practical use of bucketing techniques in computational geometry. In G. T. Toussaint, editor, Computational Geometry, pages 153-195. North-Holland, Amsterdam, Netherlands. 1985.
	BP91	J. Boner and J. Peraire. An alternating digital tree (ADT) algorithm for 3D geometric searching and intersection problems. International Journal }or Numerical Methods in Engineering, 31:1-17, 1991.
	BD95	P. Bose and L. Devroye. Intersections wit}h random geometric objects, manuscript, School of Computer Science, McGill University, 1995.
	BEY91	M. Bern, D. Eppstein, and F. Yao. The expected extremes in a Delaunay triangulation, international Journal of Computational Geometry ~4 Applications, 1:79- 91, 1991.
	Bow81	A. Bowyer. Computing Dirichlet tessel}ations. The Computer Journal, 24:162-166, 1981.
	Bri93	E. Brisson. Representing Geometric Structures in d Dimensions: Topology and Order. Discrete ~4 Computatwnal Geometry, 9(4):387-426, 1993.
	DL89	D.P. Dobkin and M. J. Laszlo. Primitives for the Manipulation of Three-Dimensional Subdivisions. AI- gorithmica, 4(1):3-32, 1989.
	DL76	D.P. Dobkin and R. J. Lipton. Mukidimensional searching problems. SIAM Journal on Computing, 5:181-186, 1976.
	DMZ95	L. Devroye, E. P. Mficke, and B. Zhu. A note on point location in Delaunay triangulations of random points. 1995. Submitted to Information Processing Letters.
	Dwy91	Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
	GH92	P.L. George and F. Hermeline. Delaunay's Mesh of a Convex Polyhedron in Dimension d. Application to Arbitrary Polyhedra. International Journal Jot Numerical Methods m Engineering, 33(5):975-995, 1!)92.
	GS78	P.J. Green and R. Sibson. Computing Dirichlet tessellations in the plane. The Computer Journal, 21:168-173, 1978.
	GS85	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	E93	Ernst P Mucke, Shapes and implementations in three-dimensional geometry, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
	PS85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

CITED BY 10

	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
	Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States
	Olivier Devillers, On deletion in Delaunay triangulations, Proceedings of the fifteenth annual symposium on Computational geometry, p.181-188, June 13-16, 1999, Miami Beach, Florida, United States
	Sunghee Choi , Nina Amenta, Delaunay triangulation programs on surface data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.135-136, January 06-08, 2002, San Francisco, California
	Olivier Devillers , Sylvain Pion , Monique Teillaud, Walking in a triangulation, Proceedings of the seventeenth annual symposium on Computational geometry, p.106-114, June 2001, Medford, Massachusetts, United States
	Bernard Chazelle , Ding Liu , Avner Magen, Sublinear geometric algorithms, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Jean-Daniel Boissonnat , Olivier Devillers , Monique Teillaud , Mariette Yvinec, Triangulations in CGAL (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.11-18, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Computational Geometry: Theory and Applications, v.28 n.2-3, p.191-215, June 2004
	V. Domiter , B. Zalik, Sweep-line algorithm for constrained Delaunay triangulation, International Journal of Geographical Information Science, v.22 n.4, p.449-462, January 2008
	Ho-Lun Cheng , Xinwei Shi, Quality mesh generation for molecular skin surfaces using restricted union of balls, Computational Geometry: Theory and Applications, v.42 n.3, p.196-206, April, 2009