Efficient algorithms for line and curve segment intersection using restricted predicates

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient algorithms for line and curve segment intersection using restricted predicates

Full text

Pdf (1.03 MB)

Source

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

Miami Beach, Florida, United States

Pages: 370 - 379

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

Jean-Daniel Boissonnat	INRIA Sophia-Antipolis
Jack Snoeyink	UBC Dept. of Comp. Sci.

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): 17, Downloads (12 Months): 61, Citation Count: 4

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/304893.304991 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	D. S. Andrews et al. Further comparison of algorithms for geometric intersection problems. in Proc. 6th Internat. Sympos. Spatial Data Handling, pages 709-724, 1994.
	2	F. Avnaim, J.-D. Boissonnat, O. Devillers, F. Preparata, and M. Yvinec. Evaluating signs of determinants using single-precision arithmetic. Algorithmica, 17(2):111-132, 1997.
	3	Ivan J. Balaban, An optimal algorithm for finding segments intersections, Proceedings of the eleventh annual symposium on Computational geometry, p.211-219, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220302]
	4	J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979.
	5	Jean-Daniel Boissonnat and Franco P. Preparata. Robust plane sweep for intersecting segments. Tech rep RR- 3270, INRIA Sophia Antipolis, Sept 1997. http ://www. inria, fr : 80/RRRT/ publicat ions-eng, html.
	6	Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Proceedings of the fourteenth annual symposium on Computational geometry, p.165-174, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276903]
	7	Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France [doi>10.1145/262839.262948]
	8	C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. Ph.D thesis, Universit~t des Saarlandes, March 1996.
	9	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]
	10	T. M. Chan. A simple trapezoid sweep algorithm for reporting red/blue segment intersections. In Proc. 6th Canad. Conf. Comput. Geom., pages 263-268, 1994.
	11	Timothy M. Y. Chan. private communication, August 1998.
	12	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
	13	K. L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd IEEE FOCS, pages 387-395, 1992.
	14	A. Robin Forrest. Invited talk on computationM geometry and software engineering. 2nd ACM SCG, 1986.
	15	Steven Fortune , Christopher J. Van Wyk, Static analysis yields efficient exact integer arithmetic for computational geometry, ACM Transactions on Graphics (TOG), v.15 n.3, p.223-248, July 1996 [doi>10.1145/231731.231735]
	16	D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
	17	John Hershberger , Subhash Suri, Applications of a semi-dynamic convex hull algorithm, BIT, v.32 n.2, p.249-267, 1992 [doi>10.1007/BF01994880]
	18	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 [doi>10.1145/262839.262922]
	19	Victor Joseph Milenkovic. Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic. PhD thesis, Carnegie-Mellon Univ, Pittsburg, PA, 1988.
	20	Larry Palazzi , Jack Snoeyink, Counting and reporting red/blue segment intersections, CVGIP: Graphical Models and Image Processing, v.56 n.4, p.304-310, July 1994 [doi>10.1006/cgip.1994.1027]
	21	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	22	Douglas M. Priest, On properties of floating point arithmetics: numerical stability and the cost of accurate computations, University of California at Berkeley, Berkeley, CA, 1992
	23	Johnathan Richard Shewchuk, Robust adaptive floating-point geometric predicates, Proceedings of the twelfth annual symposium on Computational geometry, p.141-150, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237337]
	24	K. Sugihara and M. Iri. A robust topologyoriented incremental algorithm for Voronoi diagrams. IJCGA, 4(2):179-228, 1994.
	25	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 4

	Stefan Funke , Kurt Mehlhorn, Look — a Lazy Object-Oriented Kernel for geometric computation, Proceedings of the sixteenth annual symposium on Computational geometry, p.156-165, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Olivier Devillers , Alexandra Fronville , Bernard Mourrain , Monique Teillaud, Algebraic methods and arithmetic filtering for exact predicates on circle arcs, Proceedings of the sixteenth annual symposium on Computational geometry, p.139-147, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006
	Sang Il Lee , Byoung In Cho , Jae-Kyu Lee , Seongjin Ahn , Jin Wook Chung, Visibility-based modelling and control for network-based robotics, Pattern Recognition Letters, v.30 n.11, p.968-976, August, 2009