A core library for robust numeric and geometric computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A core library for robust numeric and geometric computation

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: 351 - 359

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

V. Karamcheti	Courant Institute of Mathematical Sciences, New York University
C. Li	Courant Institute of Mathematical Sciences, New York University
I. Pechtchanski	Courant Institute of Mathematical Sciences, New York University
C. Yap	Courant Institute of Mathematical Sciences, New York University

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): 3, Downloads (12 Months): 24, Citation Count: 21

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.304989 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. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng. The SUIF compiler for scalable parallel machines. In Proceedings of the 7th SlAM Conference on Parallel Processing for Scientific Computing, 1995.
	2	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]
	3	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]
	4	C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, Efficient exact geometric computation made easy, Proceedings of the fifteenth annual symposium on Computational geometry, p.341-350, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304988]
	5	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]
	6	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]
	7	F. Chaitin-Chatelin and V. Frayssd. Lectures on Finite Precision Computations. Society for Industrial and Applied Mathematics, Philadelphia, 1996.
	8	C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
	9	Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
	10	Olivier Devillers , Franco P. Preparata, A Probabilistic Analysis of the Power of Arithmetic Filters, Brown University, Providence, RI, 1996
	11	Julian Dolby , Andrew A. Chien, An evaluation of automatic object inline allocation techniques, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-20, October 18-22, 1998, Vancouver, British Columbia, Canada
	12	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]
	13	S. J. Fortune and C. J. van Wyk. LN User Manual, 1993. AT&T Bell Laboratories.
	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	Dirk Grunwald , Benjamin Zorn, CustoMalloc: efficient synthesized memory allocators, Software—Practice & Experience, v.23 n.8, p.851-869, Aug. 1993 [doi>10.1002/spe.4380230804]
	16	Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
	17	Cart3D Homepage, 1998. Homepage for adaptive Cartesian mesh generation. URL http ://george. arc. nasa. gov/'aft o smis I cart3d/cart3d, html.
	18	CGAL Homepage, 1998. Computational Geometry Algorithms Library (CGAL) Project. A 7-institution European Community effort. See URL ht#p://wau, es .ruu.nl/.
	19	CORE Homepage, 1998. Core Library Project: URL http : / / cs. nyu. edu/exact / core/.
	20	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]
	21	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]
	22	Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Communications of the ACM, v.38 n.1, p.96-102, Jan. 1995 [doi>10.1145/204865.204889]
	23	S. Ocken, J. T. Schwartz, and M. Sharir. Precise implementation of CAD primitives using rational parameterization of standard surfaces. In J. Hopcroft, J. Schwartz, and M. Sharir, editors, Planning, Geometry, and Complexity of Robot Motion, pages 245-266. Ablex Pub. Corp., Norwood, NJ, 1987.
	24	K. Ouchi. Real/Expr: Implementation of an exact computation package. Master's thesis, New York University, Department of Computer Science, Courant Institute, January 1997.
	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	David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	27	John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
	28	John Plevyak , Xingbin Zhang , Andrew A. Chien, Obtaining sequential efficiency for concurrent object-oriented languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-321, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199524]
	29	Joonsoo Choi , Jürgen Sellen , Chee-Keng Yap, Precision-sensitive Euclidean shortest path in 3-space (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.350-359, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220317]
	30	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]
	31	David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
	32	C. Yap. A new number core for robust numerical and geometric libraries. In 3rd CGC Workshop on Geometric Computing, 1998. Invited Talk. Brown University, Oct 11-12, 1998. Abstracts in http ://www. cs. brown, edu/cgc/cgc98/home, html.
	33	Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	34	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]
	35	C. K. Yap and T. Dubd. The exact computation paradigm. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, pages 452-486. World Scientific Press, 1995. 2nd edition.
	36	Jiaxun Yu, Exact arithmetic solid modeling, Purdue University, West Lafayette, IN, 1992

CITED BY 23

	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
	C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, Efficient exact geometric computation made easy, Proceedings of the fifteenth annual symposium on Computational geometry, p.341-350, June 13-16, 1999, Miami Beach, Florida, United States
	Kurt Mehlhorn, The reliable algorithmic software challenge RASC, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	Xuejun Hao , Amitabh Varshney, Variable-precision rendering, Proceedings of the 2001 symposium on Interactive 3D graphics, p.149-158, March 2001
	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
	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
	John Keyser , Tim Culver , Mark Foskey , Shankar Krishnan , Dinesh Manocha, ESOLID---A System for Exact Boundary Evaluation, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Zhenming Chen , Evanthia Papadopoulou , Jinhui Xu, Robustness of k-gon Voronoi diagram construction, Information Processing Letters, v.97 n.4, p.138-145, 28 February 2006
	Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Exact, efficient, and complete arrangement computation for cubic curves, Computational Geometry: Theory and Applications, v.35 n.1, p.36-73, August 2006
	Eric Berberich , Michael Kerber , Michael Sagraloff, Exact geometric-topological analysis of algebraic surfaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Koji Ouchi , John Keyser, Handling degeneracies in exact boundary evaluation, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Iddo Hanniel , Ron Wein, An exact, complete and efficient computation of arrangements of Bézier curves, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	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
	Ron Wein, Exact and approximate construction of offset polygons, Computer-Aided Design, v.39 n.6, p.518-527, June, 2007
	Vikram Sharma, Complexity of real root isolation using continued fractions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Lutz Kettner , Kurt Mehlhorn , Sylvain Pion , Stefan Schirra , Chee Yap, Classroom examples of robustness problems in geometric computations, Computational Geometry: Theory and Applications, v.40 n.1, p.61-78, May, 2008
	Daniel Dumitriu , Stefan Funke , Martin Kutz , Nikola Milosavljević, How much geometry it takes to reconstruct a 2-manifold in R³, Journal of Experimental Algorithmics (JEA), 14, August 2009
	W. Dale Brownawell , Chee K. Yap, Lower bounds for zero-dimensional projections, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	W. Dale Brownawell , Chee K. Yap, Lower bounds for zero-dimensional projections, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	Ron Wein , Efi Fogel , Baruch Zukerman , Dan Halperin, Advanced programming techniques applied to Cgal's arrangement package, Computational Geometry: Theory and Applications, v.38 n.1-2, p.37-63, September, 2007