Efficient exact geometric computation made easy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient exact geometric computation made easy

Full text

Pdf (1.09 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: 341 - 350

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

C. Burnikel	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
R. Fleischer	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
K. Mehlhorn	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
S. Schirra	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany

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): 37, Citation Count: 12

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.304988 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	S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Inform. Process. Lett,, 7(5):219-222, 1978.
	2	Johannes Blömer, A Probabilistic Zero-Test for Expressions Involving Root of Rational Numbers, Proceedings of the 6th Annual European Symposium on Algorithms, p.151-162, August 24-26, 1998
	3	H." BrSnniman, L. Kettner, S. Schirra, and R. Veltkamp. Applications of the generic programming paradigm in the design of CGAL. Research Report MPI-I-98-1-030, Max-Planck-insitut fiir Informatik, 1998.
	4	C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra. Companion page to 'Efficient exact geometric computation made easy', http:/www.mpi-sb, mpg. de / "" st s chirr / exact/made _easy.
	5	C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, A strong and easily computable separation bound for arithmetic expressions involving square roots, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.702-709, January 05-07, 1997, New Orleans, Louisiana, United States
	6	Christoph Burnikel , Stefan Funke , Michael Seel, Exact geometric predicates using cascaded computation, Proceedings of the fourteenth annual symposium on Computational geometry, p.175-183, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276904]
	7	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]
	8	C. Burnikel, K. Mehlhorn, and S. Schirra. The LEDA class real number. Research Report MPI-I-96-1- 001, Max-Planck-Institut f/ir Informatik, 1996. A more recent documentation of the implementation is available at http://w,m.mpi-sb.mpg.de/'burnikel/ report s/real, ps. gz.
	9	CGAL project, http://m,m.cs.uu.nl/CGAL/.
	10	T. J. Dekker. A floating-point technique for extending the available precision. Numerische Mathematik, 18:224 - 242, 1971.
	11	Andreas Fabri , Geert-Jan Giezeman , Lutz Kettner , Stefan Schirra , Sven Schönherr, The CGAL Kernel: A Basis for Geometric Computation, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.191-202, May 27-28, 1996
	12	A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. SchSnherr. On the design of CGAL, the computational geometry algorithms library. Research Report MPI-I-98-1-007, Max-Planck-Institut ffir Informatik, 1998.
	13	S. Fortune. Progress in computational geometry. In R. Martin, editor, Directions in Geometric Computing, pages 81 - 128. Information Geometers Ltd., 1993.
	14	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]
	15	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]
	16	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 [doi>10.1145/304893.304989]
	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	J. Keyser. personal communication.
	19	John Keyser , Tim Culver , Dinesh Manocha , Shankar Krishnan, MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
	20	K. Mehlhorn and S. N#her. The implementation of geometric algorithms. In Proceedings of the 13th IFIP World Computer Congress, volume 1, pages 223- 231. Elsevier Science B.V. North-Holland, Amsterdam, 1994.
	21	Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
	22	K. Mehlhorn, S. N/iher, M. Seel, and C. Uhrig. The LEDA User manual, 3.7 edition, 1998. see http:// www. mpi- sb .mpg. de/LEDA/leda, html.
	23	D. Michelucci. A quadratic non-standard arithmetic. In Prec. 9th Canadian Conf. on Comp. Geom., 1997. http://#, emse. fr/'micheluc/english/ quadrat ique. html.
	24	K. Ouchi. Real/Expr: Implementation of exact computation. Courant Institute, New York University, 1997. Master thesis, h'ctp://cs.nyu.edu/exact/ realexpr.
	25	Mark H. Overmars, Designing the Computational Geometry Algorithms Library CGAL, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.53-58, May 27-28, 1996
	26	D. M. Priest. Algorithms for arbitrary precision floating point arithmetic. In l Oth Symposium on Computer Arithmetic, pages 132 - 143. IEEE Computer Society Press, 1991.
	27	A. Rege. APU User Manual - Version 2.0, 1996. http ://www. cs. berkeley, edu/'rege/apu/apu, html.
	28	Stefan Schirra, Precision and Robustness in Geometric Computations, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.255-287, September 16-20, 1996
	29	Stefan Schirra, A Case Study on the Cost of Geometric Computing, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.156-176, January 15-16, 1999
	30	J. R. Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete and Computational Geometry 18:305-363, 1997.
	31	R. C. Veltkamp. Generic programming in cgal, the computational geometry algorithms library. In Proceedings of the 6th Eurographics Workshop on Programming Paradigms in Graphics, 1997.
	32	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]
	33	Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	34	C. K. Yap and T. DubS. The exact computation paradigm. In D. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 452-492. World Scientific Press, 1995. 2nd edition.

CITED BY 12

	Chen Li , Chee Yap, A new constructive root bound for algebraic expressions, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.496-505, January 07-09, 2001, Washington, D.C., United States
	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
	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
	Brian P. Gerkey , Sebastian Thrun , Geoff Gordon, Visibility-based Pursuit-evasion with Limited Field of View, International Journal of Robotics Research, v.25 n.4, p.299-315, April 2006
	Shankar Krishnan , Mark Foskey , Tim Culver , John Keyser , Dinesh Manocha, PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation, Proceedings of the seventeenth annual symposium on Computational geometry, p.274-283, June 2001, Medford, Massachusetts, United States
	Ee-Chien Chang , Sung Woo Choi , DoYong Kwon , Hyungju Park , Chee K. Yap, Shortest path amidst disc obstacles is computable, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Sylvain Pion , Chee K. Yap, Constructive root bound for <tt>k</tt>-ary rational input numbers, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Brian E. Weinrich , Markus Schneider, Use of rational numbers in the design of robust geometric primitives for three-dimensional spatial database systems, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany
	Sylvain Pion , Chee K. Yap, Constructive root bound for k-ary rational input numbers, Theoretical Computer Science, v.369 n.1, p.361-376, 15 December 2006
	Erik D. Demaine , Mihai Patrascu, Tight bounds for dynamic convex hull queries (again), Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Alexey Lvov , Ulrich Finkler, Exact basic geometric operations on arbitrary angle polygons using only fixed size integer coordinates, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Brian P. Gerkey , Sebastian Thrun , Geoff Gordon, Visibility-based pursuit-evasion with limited field of view, Proceedings of the 19th national conference on Artifical intelligence, p.20-27, July 25-29, 2004, San Jose, California