Robust proximity queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Robust proximity queries: an illustration of degree-driven algorithm design

Full text

Pdf (1.50 MB)

Source

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

Nice, France

Pages: 156 - 165

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Giuseppe Liotta	Dipartimento di Informatica e Sistemistica, Universitá di Roma "La Sapienza", Via Salaria 113, Roma 00198, Italy
France P. Preparata	Center for Geometric Computing, Department of Computer Science, Brown University, 115 Waterman Street, Providence, RI
Roberto Tamassia	Center for Geometric Computing, Department of Computer Science, Brown University, 115 Waterman Street, Providence, RI

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): 2, Downloads (12 Months): 8, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.262922 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	M. Bocher. Introduction to higher algebra. Macmillan, 1907.
	2	C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. Ph.D thesis, Universit#t des Saarlandes, Mar. 1996.
	3	C. Burnikel , J. Könemann , K. Mehlhorn , S. Näher , S. Schirra , C. Uhrig, Exact geometric computation in LEDA, Proceedings of the eleventh annual symposium on Computational geometry, p.418-419, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220330]
	4	Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, On degeneracy in geometric computations, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.16-23, January 23-25, 1994, Arlington, Virginia, United States
	5	Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
	6	K. L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd Annu. IEEE Sympos. Found. Cornput. Sci., pages 387-395, 1992.
	7	D. P. Dobkin. Computational geometry and computer graphics. Proc. IEEE, 80(9):1400-1411, Sept. 1992.
	8	D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection. Theoret. Comput. Sci., 27:241- 253, 1983.
	9	D. P. Dobkin and M. J. Laszlo. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica, 4:3-32, 1989.
	10	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	11	H. Edelsbrunner and H. A. Maurer. Finding extreme points in three dimensions and solving the post-office problem in the plane. Inform. Process. Left., 21:39-47, 1985.
	12	S. Fortune. Stable maintenance of point set triangulations in two dimensions. In Proc. 30th Annu. IEEE Sympos. Found. Comput. Sci., pages 494-505, 1989.
	13	Steven Fortune , Christopher J. Van Wyk, Efficient exact arithmetic for computational geometry, Proceedings of the ninth annual symposium on Computational geometry, p.163-172, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161015]
	14	L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992.
	15	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]
	16	Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
	17	Michael Karasick , Derek Lieber , Lee R. Nackman, Efficient Delaunay triangulation using rational arithmetic, ACM Transactions on Graphics (TOG), v.10 n.1, p.71-91, Jan. 1991 [doi>10.1145/99902.99905]
	18	D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12:28-35, 1983.
	19	D. T. Lee and F. P. Preparata. Location of a point in a planar subdivision and its applications. SIAM J. Comput., 6:594-606, 1977.
	20	Giuseppe Liotta , Franco P. Preparata , Roberto Tamassia, Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design, SIAM Journal on Computing, v.28 n.3, p.864-889, Feb. 1999 [doi>10.1137/S0097539796305365]
	21	F. P. Preparata. A new approach to planar point location. SIAM J. Comput., 10:473-482, 1981.
	22	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	23	Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
	24	Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
	25	K. Sugihara and M. Iri. Construction of the Voronoi diagram for 'one million' generators in single-precision arithmetic. Proc. IEEE, 80(9):1471-1484, Sept. 1992.
	26	It. Tamassia and J. S. Vitter. Optimal cooperative search in fractional cascaded data structures. Algorithmica, 15(2), 1996.
	27	C.-K. Yap, Symbolic treatment of geometric degeneracies, Journal of Symbolic Computation, v.10 n.3-4, p.349-370, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80069-7]
	28	Chee-Keng Yap, Towards exact geometric computation, Computational Geometry: Theory and Applications, v.7 n.1-2, p.3-23, Jan. 1997 [doi>10.1016/0925-7721(95)00040-2]

CITED BY 2

	Jean-Daniel Boissonnat , Jack Snoeyink, Efficient algorithms for line and curve segment intersection using restricted predicates, Proceedings of the fifteenth annual symposium on Computational geometry, p.370-379, June 13-16, 1999, Miami Beach, Florida, United States
	V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States