Static analysis yields efficient exact integer arithmetic for computational geometry

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Static analysis yields efficient exact integer arithmetic for computational geometry

Full text

Pdf (1.91 MB)

Source

ACM Transactions on Graphics (TOG) archive
Volume 15 , Issue 3 (July 1996) table of contents

Pages: 223 - 248

Year of Publication: 1996

ISSN:0730-0301

Authors

Steven Fortune	AT&T Bell Laboratories, Murray Hill, NJ
Christopher J. Van Wyk	Dept. of Mathematics and Computer Sceince, Drew University, Madison, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 36, Citation Count: 19

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/231731.231735 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	F. Avnaim , J.-D. Boissonnat , O. Devillers , F. P. Preparata , M. Yvinec, Evaluation of a new method to compute signs of determinants, Proceedings of the eleventh annual symposium on Computational geometry, p.416-417, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220329]
	2	Richard P. Brent, Algorithm 524: MP, A Fortran Multiple-Precision Arithmetic Package [A1], ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.71-81, March 1978 [doi>10.1145/355769.355776]
	3	Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results, Proceedings of the Second Annual European Symposium on Algorithms, p.227-239, September 26-28, 1994
	4	BENOUAMER, M. O., JAmLON, P., MICHELUCCI, D., AND MOREAU, J.-M. 1993. A "lazy" solution to imprecision in computational geometry. In Proceedings of the Fifth Canadian Conference on Computational Geometry (Waterloo, Ontario, Aug. 5-9), 73-78,
	5	BENOUAMER, M. O., MICHELUCCI, D., AND PEROCHE, B. 1994. Error-free boundary evaluation based on a lazy rational arithmetic: a detailed implementation. Comput.-Aided Des. 26, 6, 403-416.
	6	BENTLEY, J. L. AND OTTMANN, T.A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28, 9 (Sept.), 643-647.
	7	Tom Cargill, C++ programming style, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	8	CHANG, J. AND MILENKOVIC, V. 1993. An experiment using LN for exact geometric computations. In Proceedings of the 5th Canadian Conference on Computational Geometry (Waterloo, Ontario, Aug. 5-9), 67-72.
	9	CLARKSON, K.L. 1992. Safe and effective determinant evaluation. In the 33th Symposium on Foundations of Computer Science (Pittsburgh, PA, Oct. 24-27), 387-395.
	10	Dus~, T~ AND YAP, C.K. 1994. A basis for implementing exact geometric algorithms. Manuscript.
	11	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	12	FORTUNE, S. 1993. Progress in computational geometry, Ch. 3. In Directions in Geometric Computing, R. Martin, Ed., Information Geometers Ltd, 81-128.
	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	FORTt'NE, S. AND VAN WYK, C. 1993. LN users manual. Manuscript, AT&T Bell Laboratories.
	15	Steven Fortune, Polyhedral modelling with exact arithmetic, Proceedings of the third ACM symposium on Solid modeling and applications, p.225-234, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218065]
	16	FORTUNE, S. 1995b. Numerical stability of algorithms for 2D Delaunay triangulations, Int. J. Comput. Geom. Appl. 5, l, 2, 193-213.
	17	GREENE, D. AND YAO, F. 1986. Finite-resolution computational geometry. In Proceedings of the 27th Annual Symposium on the Foundations of Computer Science, (Toronto, Ontario, Oct. 27-29), 143-152.
	18	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]
	19	HoBsY, J. 1993. Practical segment intersection with finite precision output. Submitted.
	20	Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	21	JAILLON, P. 1993. Proposition d'une arithm~tique rationnelle paresseuse et d'un outil d'aide la saisie d'objets en synth~se d'images, Thbse, Ecole Nationale Superieure des Mines de Saint-Etienne. URL: http://www.emse.fr/pub/papers/LAZY/thesePJ.ps.Z.
	22	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]
	23	Zhenyu Li , Victor Milenkovic, Constructing strongly convex hulls using exact or rounded arithmetic, Proceedings of the sixth annual symposium on Computational geometry, p.235-243, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98577]
	24	MEHLHORN, K. AND NAHER, S. 1994. Implementation of a sweepline algorithm for the straight line segment intersection problem. Manuscript.
	25	MILENKOVIC, V. 1989. Rounding face lattices in the plane. In First Canadian Conference on Computational Geometry (Montreal, Quebec, Aug. 21-25).
	26	NAHER, S. 1995. The LEDA User Manual. Ver. 3.1, Jan. 16, LEDA is available by anonymous FTP from ftp.mpi-sb.mpg.de in directory/pub/LEDA.
	27	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
	28	SERPETTE, B., VUILLEMIN, J., AND HERVE, J.C. 1989. BigNum: a portable and efficient package for arbitrary-precision arithmetic. Res. Rep. 2, Digital Paris Research Laboratory, May.
	29	SHEWCHUK, J.g. 1995. Adaptive precision floating-point arithmetic and fast robust geometric predicates in C. Res. Rep., Carnegie-Mellon Univ., Dec.
	30	SUGII~mA, K. AND IRI, M. 1989. Construction of the Voronoi diagram for one million generators in single precision arithmetic. In First Canadian Conference on Computational Geometry (Montreal, Quebec, Aug. 21-25).
	31	K. Sugihara , M. Iri, A solid modelling system free from topological inconsistency, Journal of Information Processing, v.12 n.4, p.380-393, 1989
	32	VAN WYE, C. 1994. Plane sweep with efficient exact arithmetic. Manuscript.
	33	VAN WYK, C. 1995. Missing real numbers. Am. Math. Monthly 105, 260-265.
	34	YAP, C. 1993. Towards exact geometric computation. In Proceedings of the Fifth Canadian Conference on Computational Geometry (Waterloo, Ontario, Aug. 5-9), 405-419.
	35	YAP, C. AND DUBS T. 1995. The exact computation paradigm. In Computing in Euclidean Geometry. D. Z. Du, F. Hwang, Eds, World Scientific, 2nd ed., 452-492.

CITED BY 19

	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
	Sigal Raab, Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes, Proceedings of the fifteenth annual symposium on Computational geometry, p.163-172, June 13-16, 1999, Miami Beach, Florida, United States
	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
	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
	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
	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
	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
	Xuejun Hao , Amitabh Varshney, Variable-precision rendering, Proceedings of the 2001 symposium on Interactive 3D graphics, p.149-158, March 2001
	Steven Fortune, Vertex-rounding a three-dimensional polyhedral subdivision, Proceedings of the fourteenth annual symposium on Computational geometry, p.116-125, June 07-10, 1998, Minneapolis, Minnesota, United States
	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
	Dan Halperin , Christian R. Shelton, A perturbation scheme for spherical arrangements with application to molecular modeling, Proceedings of the thirteenth annual symposium on Computational geometry, p.183-192, June 04-06, 1997, Nice, France
	Steven Fortune, Topological beam tracing, Proceedings of the fifteenth annual symposium on Computational geometry, p.59-68, June 13-16, 1999, Miami Beach, Florida, United States
	Steven Fortune, Exact computations of the inertia symmetric integer matrices, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.556-564, May 21-23, 2000, Portland, Oregon, United States
	Dan Halperin , Eran Leiserowitz, Controlled perturbation for arrangements of circles, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Eyal Flato , Dan Halperin , Iddo Hanniel , Oren Nechushtan , Eti Ezra, The design and implementation of panar maps in CGAL, Journal of Experimental Algorithmics (JEA), 5, p.13-es, 2000
	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
	Martin Ziegler, Stability versus speed in a computable algebraic model, Theoretical Computer Science, v.351 n.1, p.14-26, 14 February 2006
	Susan Hert , Michael Hoffmann , Lutz Kettner , Sylvain Pion , Michael Seel, An adaptable and extensible geometry kernel, Computational Geometry: Theory and Applications, v.38 n.1-2, p.16-36, September, 2007
	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