Towards implementing robust geometric computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards implementing robust geometric computations

Full text

Pdf (645 KB)

Source

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

Urbana-Champaign, Illinois, United States

Pages: 106 - 117

Year of Publication: 1988

ISBN:0-89791-270-5

Authors

C. M. Hoffmann	Computer Science Department, Purdue University
J. E. Hopcroft	Computer Science Department, Cornell University
M. S. Karasick	Computer Science Department, Cornell and McGill Universities

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 30, Citation Count: 21

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/73393.73405 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. Durrant-Whyte (1986) "Concerning Uncertain Geometry in Robotics," International Workshop on Geometric Reasoning, Oxford, England, July 1986.
	2	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	3	G. Golub and C. van Loan (1983) "Matrix Computation," Johns Hopkins Press, Baltimore.
	4	D. Greene, F. Yao (1986) "Finite-Resolution Computational Geometry," Proc. 27th IEEE Symp. on Found. Comp. Sci., Toronto, 143- 152.
	5	Christoph M. Hoffmann , John E. Hopcroft , Michael S. Karasick, Robust Set Operations on Polyhedral Solids, Cornell University, Ithaca, NY, 1987
	6	M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
	7	J. C. Lagarias, The computational complexity of simultaneous diophantine approximation problems, SIAM Journal on Computing, v.14 n.1, p.196-209, Feb. 1985 [doi>10.1137/0214016]
	8	V. J. Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, Geometric reasoning, MIT Press, Cambridge, MA, 1989
	9	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]
	10	K. Sugihara (1987) "An approach to error-free solid modeling," Notes, instit, for Math. and Applic., Univ. of Minnesota
	11	K. Sugihara (1987) "On finite precision representations of geometric objects," Res. Memo RMI 87.06, Dept. of Math. Engr., Univ. of Tokyo

CITED BY 21

	D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany
	Christoph M. Hoffmann , John E. Hopcroft , Michael E. Karasick, Robust Set Operations on Polyhedral Solids, IEEE Computer Graphics and Applications, v.9 n.6, p.50-59, November 1989
	Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989
	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
	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
	Mark Segal, Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.105-114, Aug. 1990
	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
	John Canny , Bruce Donald , Eugene K. Ressler, A rational rotation method for robust geometric algorithms, Proceedings of the eighth annual symposium on Computational geometry, p.251-260, June 10-12, 1992, Berlin, Germany
	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
	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
	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
	S. R. Ala, Design methodology of boundary data structures, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.13-23, June 05-07, 1991, Austin, Texas, United States
	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
	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
	M. Gangnet , J.-C. Hervé , T. Pudet , J.-M. van Thong, Incremental computation of planar maps, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.345-354, July 1989
	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
	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
	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
	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
	C. M. Hoffmann , N. F. Stewart, Accuracy and semantics in shape-interrogation applications, Graphical Models, v.67 n.5, p.373-389, September 2005
	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