Numerical stability of geometric algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Numerical stability of geometric algorithms

Full text

Pdf (796 KB)

Source

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

Waterloo, Ontario, Canada

Pages: 119 - 125

Year of Publication: 1987

ISBN:0-89791-231-4

Authors

T. Ottmann	Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West Germany
G. Theimt	Institut für Angewandte Informatik, und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, D-7500 Karlsrube, West Germany
C. Ullrich	Institut für Angewandte Mathematik, Universität Karlsruhe, Postfach 6980, D-7500 Karlsruhe, West Germany

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): 4, Downloads (12 Months): 20, Citation Count: 14

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/41958.41970 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.

	P	V. Akman: Shortest Paths Avoiding Polyhedral Obstacles in 3-Dimensional Euclidean Space, IPL-TR-075, Rensselaer Polytechnic Institute, Troy, New York 12181, 1986.
	Ber	G.B. Beretta: An implementation of a plane sweep-algorithm on a personal computer, Dr.- Dissertation, Eidgeniissische Technische Hochschule Ziirich, 1984.
	Bo	J.L. Bentley, Th. Ottmann: Algorithms for reporting and counting geometric intersecitons, IEEE Transactions on Computers, 28, p. 643- 647, 1979.
	BRUW	Gerd Bohlender , Christian Ullrich , Jürgen Wolff von Gudenberg , Louis B. Rall, Pascal-SC: a computer language for scientific computation, Academic Press Professional, Inc., San Diego, CA, 1987
	IF	A. R. Forrest: Computational Geometry and Software Engineering: Towards a Geometric Computing Environment, to be published in "State-of-the-Art in Computer Graphics", Eds. 11. A. Earnshaw and D. F. Rogers, Springer Verlag, March 1987.
	GS	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]
	KM1	Ulrich W. Kulisch , Willard L. Miranker, Computer Arithmetic in Theory and Practice, Academic Press, Inc., Orlando, FL, 1981
	KM2	U. Ku&h, W.L. Miranker feds.): A New Approach to Scientific Computation, Academic Press, New York, 1983.
	LP	D.T. Lee, F.P. Preparata: Computational Geometry - A Survey, IEEE Transactions on Computers, vol. C-33, no. 12,1072-1101, 1984.
	M	Mathlab Group: MACSYMA Reference Manual, 2 vols., Lab. for Computer Science, Massachusetts Inst. of Technology, Cambridge, MA, 1983.
	Me	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	P3	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Ra	L. Ramshaw: CSL Notebook Entry: The Braiding of Floating Point Lines, unpublished note, Xerox PARC, Oct. 1982.
	R	S.M. Rump: Solving Nonlinear Systems with Least Significant Bit Accuracy, Computing 29, p. 183-200, 1982.
	RB	S.M. Rump, H. Blihm: Least Significant Bit Evaluation of Arithmetic Expressions in Single- Precision, Computing 3013, p. 189-199, 1983.
	Th	G. Thiemt: Die numerische Stabilitlt geometrischer Algorithmen, Diploma Thesis, Karlsruhe, Oktober 1986.
	To	Toussaint, G. (Ed.): Computational Geometry, Elsevier North Holland, N.Y., 1985.

CITED BY 14

	Mark Segal, Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.105-114, Aug. 1990
	Walter Gish , Allen Tanner, Hardware antialiasing of lines and polygons, Proceedings of the 1992 symposium on Interactive 3D graphics, p.75-86, June 1992, Cambridge, Massachusetts, United States
	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
	Xiaohong Zhu , Shiaofen Fang , Beat D. Brüderlin, Obtaining robust Boolean set operations for manifold solids by avoiding and eliminating redundancy., Proceedings on the second ACM symposium on Solid modeling and applications, p.147-154, May 19-21, 1993, Montreal, Quebec, Canada
	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
	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
	D. P. Dobkin , D. Silver, Recipes for geometry and numerical analysis - Part I: an empirical study, Proceedings of the fourth annual symposium on Computational geometry, p.93-105, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Kokichi Sugihara, An Intersection Algorithm Based on Delaunay Triangulation, IEEE Computer Graphics and Applications, v.12 n.2, p.59-67, March 1992
	Kurt Mehlhorn, The reliable algorithmic software challenge RASC, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	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
	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
	Hiroshi Nagamochi , Kengo Iwata , Toshimasa Ishii, A robust algorithm for bisecting a triconnected graph with two resource sets, Theoretical Computer Science, v.341 n.1, p.364-378, 5 September 2005
	Jose Antonio Cotelo Lema , Ralf Hartmut Güting, Dual Grid: A New Approach for Robust Spatial Algebra Implementation, Geoinformatica, v.6 n.1, p.57-76, March 2002