Robust adaptive floating-point geometric predicates

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Robust adaptive floating-point geometric predicates

Full text

Pdf (1.25 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 141 - 150

Year of Publication: 1996

ISBN:0-89791-804-5

Author

Johnathan Richard Shewchuk

School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania

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): 35, Citation Count: 16

Additional Information:

references cited by index terms

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/237218.237337 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	Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, Franco P. Preparata, and Mariette Yvinec. Evaluating Signs of Determinants Using Single-Precision Arithmetic. 1995.
	2	David H. Bailey. A Portable High Performance Multiprecision Package. Technical Report RNR-90-022, NASA Ames Research Center, May 1993.
	3	Kenneth L. Clarkson. Safe and Effective Determinant Evaluation. 33rd Annual Symposium on Foundations of Computer Science, pages 387-395, 1992.
	4	T.J. Dekker. A Floating-Point Technique for Extending the Available Precision. Numerische Mathematik 18:224-242, 1971.
	5	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]
	6	Static Analysis Yields Efficient Exact Integer Arithmetic for Computational Geometry. To appear in Transactions on Mathematical Software, 1996.
	7	David Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys (CSUR), v.23 n.1, p.5-48, March 1991 [doi>10.1145/103162.103163]
	8	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]
	9	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]
	10	Donald Ervin Knuth. The Art of Computer Programming: Seminumerical Algorithms, second edition, volume 2. Addison Wesley, 1981.
	11	D. T. Lee and B. J. Schachter. Two Algorithms for Constructing a Delaunay Triangulation. Int. J. Comput. Inf. Sci. 9:219-242, 1980.
	12	Douglas M. Priest. Algorithms for Arbitrary Precision Floating Point Arithmetic. Tenth Symposium on Computer Arithmetic, pages 132- I43, 1991.
	13	On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. Ph.D. thesis, Department of Mathematics, University of California at Berkeley, November 1992.
	14	Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
	15	David F. Watson. Computing the r~-dimenstonal Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal 24:167-172, 1981.

CITED BY 16

	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
	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
	Hervé Brönnimann , Mariette Yvinec, Efficient exact evaluation of signs of determinants, Proceedings of the thirteenth annual symposium on Computational geometry, p.166-173, June 04-06, 1997, Nice, France
	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
	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
	T. M. Murali , Thomas A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 symposium on Interactive 3D graphics, p.155-ff., April 27-30, 1997, Providence, Rhode Island, 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
	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
	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
	Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
	Michal Varnuska , Ivana Kolingerova, Improvements to surface reconstruction by the CRUST algorithm, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia
	Jean-Daniel Boissonnat , Olivier Devillers , Monique Teillaud , Mariette Yvinec, Triangulations in CGAL (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.11-18, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	J. Andreas Baerentzen , Henrik Aanaes, Signed Distance Computation Using the Angle Weighted Pseudonormal, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.243-253, May 2005
	Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Computational Geometry: Theory and Applications, v.28 n.2-3, p.191-215, June 2004
	Hesheng Bao , Jacobo Bielak , Omar Ghattas , Loukas F. Kallivokas , David R. O'Hallaron , Jonathan R. Shewchuk , Jifeng Xu, Earthquake ground motion modeling on parallel computers, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.13-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	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