Epsilon geometry: building robust algorithms from imprecise computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Epsilon geometry: building robust algorithms from imprecise computations

Full text

Pdf (1.13 MB)

Source

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

Saarbruchen, West Germany

Pages: 208 - 217

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

D. Salesin	Stanford University
J Stolfi	DEC Systems Research Center
L. Guibas	Stanford University and DEC Systems Research Center

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): 7, Downloads (12 Months): 60, Citation Count: 26

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/73833.73857 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	H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73406]
	2	Daniel H. Greene and F. Frances Yao, "Finiteresolution computational geometry." Proc. 27th IEEE Symp. on the Foundations of Computer Science (1986), 143-152.
	3	C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
	4	Leo Guibas, Lyle Ramshaw, and Jorge Stolfi, "A kinetic framework for computational geometry." Proc. 24th IEEE Symp. on Foundations of Computer Science (October 1983), 100-111.
	5	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	6	Victor J. Milenkovic, "Verifiable implementations of geometric algorithms using finite precision arithmetic." International Workshop on Geometric Reasoning (Oxford, England, July 1986).
	7	S. P. Mudur and P. A. Koparkar, "Interval methods for processing geometric objects." IEEE Computer Graphics and Applications (February 1984), 7-17.
	8	T. Ottmann , G. Theimt , C. Ullrich, Numerical stability of geometric algorithms, Proceedings of the third annual symposium on Computational geometry, p.119-125, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41970]
	9	C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

CITED BY 27

	Mark Segal, Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.105-114, Aug. 1990
	J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States
	Gill Barequet , Stina S. Bridgeman , Christian A. Duncan , Michael T. Goodrich , Roberto Tamassia, Classical computational geometry in GeomNet, Proceedings of the thirteenth annual symposium on Computational geometry, p.412-414, June 04-06, 1997, Nice, France
	M. Benouamer , D. Michelucci , B. Peroche, Error-free boundary evaluation using lazy rational arithmetic: a detailed implementation, Proceedings on the second ACM symposium on Solid modeling and applications, p.115-126, May 19-21, 1993, Montreal, Quebec, Canada
	Abbas Edalat , André Lieutier, Foundation of a computable solid modeling, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.278-284, June 08-11, 1999, Ann Arbor, Michigan, United States
	Francesca Coppa , Enrico Nardelli , Maurizio Talamo, A formal model for the discrete representation of spatial objects, Proceedings of the 1997 ACM symposium on Applied computing, p.144-151, April 1997, San Jose, California, United States
	Maged S. Tawfik, An efficient algorithm for CSG to b-rep conversion, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.99-108, June 05-07, 1991, Austin, Texas, 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
	Steven Fortune , Victor Milenkovic, Numerical stability of algorithms for line arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.334-341, June 10-12, 1991, North Conway, New Hampshire, United States
	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
	Yossi Matias , Jeffrey Scott Vitter , Neal E. Young, Approximate data structures with applications, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.187-194, January 23-25, 1994, Arlington, Virginia, United States
	Michael T. Goodrich , Leonidas J. Guibas , John Hershberger , Paul J. Tanenbaum, Snap rounding line segments efficiently in two and three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.284-293, June 04-06, 1997, Nice, France
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Christopher Gold, Crust and anti-crust: a one-step boundary and skeleton extraction algorithm, Proceedings of the fifteenth annual symposium on Computational geometry, p.189-196, June 13-16, 1999, Miami Beach, Florida, United States
	Wei Chen , Koichi Wada , Kimio Kawaguchi, Parallel robust algorithms for constructing strongly convex hulls, Proceedings of the twelfth annual symposium on Computational geometry, p.133-140, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Florent Duguet , George Drettakis, Robust epsilon visibility, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	Abbas Edalat , André Lieutier, Foundation of a computable solid modelling, Theoretical Computer Science, v.284 n.2, p.319-345, 28 July 2002
	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
	Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: nearest neighbor relations for imprecise points, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Leonidas J. Guibas , David H. Marimont, Rounding arrangements dynamically, Proceedings of the eleventh annual symposium on Computational geometry, p.190-199, June 05-07, 1995, Vancouver, British Columbia, Canada
	Dominique Michelucci , Jean-Michel Moreau, Lazy Arithmetic, IEEE Transactions on Computers, v.46 n.9, p.961-975, September 1997
	Wei Chen , Koichi Wada , Kimio Kawaguchi, Robust algorithms for constructing strongly convex hulls in parallel, Theoretical Computer Science, v.289 n.1, p.277-295, 23 October 2002
	V. Milenkovic, Calculating approximate curve arrangements using rounded arithmetic, Proceedings of the fifth annual symposium on Computational geometry, p.197-207, June 05-07, 1989, Saarbruchen, West Germany
	Daniel Russel , Menelaos I. Karavelas , Leonidas J. Guibas, A package for exact kinetic data structures and sweepline algorithms, Computational Geometry: Theory and Applications, v.38 n.1-2, p.111-127, September, 2007
	Maarten Löffler , Jack Snoeyink, Delaunay triangulations of imprecise pointsin linear time after preprocessing, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	A. Haselbacher , F. M. Najjar , J. P. Ferry, An efficient and robust particle-localization algorithm for unstructured grids, Journal of Computational Physics, v.225 n.2, p.2198-2213, August, 2007