Numerical stability of algorithms for line arrangements

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Numerical stability of algorithms for line arrangements

Full text

Pdf (805 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 334 - 341

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Steven Fortune	AT&T Bell Laboratories, Murray Hill, New Jersey
Victor Milenkovic	Harvard University, Cambridge, Massachusetts

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): 13, Citation Count: 9

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/109648.109685 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	B. Chazelle, L.J. Guibas, D.T. Lee. The power of geometric duality, ~dth Annual Symposium on the Foundations of Computer Science, pages 217-225, IEEE, 1983.
	2	H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
	3	H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing Arrangements of Lines and Hyperplanes with Applications, 2~th Annual Symposium on the Foundations of Computer Science, pages 83-91, IEEE, 1983.
	4	Steven Fortune. Stable Maintenance of Point-Set Triangulation in Two Dimensions, manuscript, 1990, ATT Bell Laboratories. An abbreviated version appeared in 80th Annual Symposium on the Foundations of Computer Science, IEEE, October 1989.
	5	Jonathan L. Gross , Thomas W. Tucker, Topological graph theory, Wiley-Interscience, New York, NY, 1987
	6	Branko Grunbaum. Arrangement and Spreads, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10, American Mathematical Society, 1972.
	7	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 [doi>10.1145/73833.73857]
	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	Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
	10	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]
	11	John E. Hopcroft , Peter J. Kahn, A Paradigm for Robust Geometric Algorithms, Cornell University, Ithaca, NY, 1989
	12	M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
	13	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]
	14	Victor Milenkovic. Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic, 30th Annual Symposium on the Foundations of Computer Science, IEEE, October 1989.
	15	Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
	16	Victor Joseph Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, 1988
	17	N.E. Mnev. The Universality theorems on the classification problem of configuration varieties and convex polytopes varieties, O.Y. Viro, ed., it Topology and Geometry- Rohlin Seminar, LN Mathematics, 1346, pp. 527-544, Springer-Verlag, 1989.
	18	K. Sugihara, M. Iri, Geometric Algorithms in Finite- Precision Arithmetic, Research Memorandum RMI 88- 10, University of Tokyo, September, 1988.
	19	K. Sugihara, M. iri, Construction of the Voronoi Diagram for One Million Generators in Single Precision Arithmetic, First Canadian Conference on Computational Geometry, Montreal, Canada, 1989.

CITED BY 8

	Chandrajit L. Bajaj , Valerio Pascucci, Splitting a complex of convex polytopes in any dimension, Proceedings of the twelfth annual symposium on Computational geometry, p.88-97, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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
	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
	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
	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
	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
	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
	Stefan Funke , Kurt Mehlhorn , Stefan Näher, Structural filtering: a paradigm for efficient and exact geometric programs, Computational Geometry: Theory and Applications, v.31 n.3, p.179-194, June 2005