Article

Free access

Numerical stability of algorithms for line arrangements

Authors:

Steven Fortune,

Victor MilenkovicAuthors Info & Claims

SCG '91: Proceedings of the seventh annual symposium on Computational geometry

Pages 334 - 341

https://doi.org/10.1145/109648.109685

Published: 01 June 1991 Publication History

PDF eReader

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.

Google Scholar

[2]

H. Edelsbrunner and L. Guibas. Topologically Sweeping and Arrangement Proceedings of the Symposium on Computational Geometry, pages 389-403, ACM, June 1986.

Digital Library

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[5]

J. L. Gross, T. W. Tucker. Topological Graph Theory, John Wiley and Sons, 1987.

Digital Library

Google Scholar

[6]

Branko Grunbaum. Arrangement and Spreads, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10, American Mathematical Society, 1972.

Crossref

Google Scholar

[7]

Leonidas Guibas, David Salesin, and Jorge Stolfi. Epsilon Geometry: Building Robust Algorithms from Imprecise Computations, Proceedings of the Symposium on Computational Geometry, pages 208-217, ACM, June 1989.

Digital Library

Google Scholar

[8]

L. Guibas, J. Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics, 4:74-123, 1985.

Digital Library

Google Scholar

[9]

C. Hoffmann. The Problems of Accuracy and Robustness in Geometric Computation, Computer, Vol. 22, No. 3, March 1989, pp. 31-42.

Digital Library

Google Scholar

[10]

C. Hoffmann, J. Hopcroft, M. Karasick. Towards Implementing Robust Geometric Computations, Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 106-117.

Digital Library

Google Scholar

[11]

J. Hopcroft, P. Kahn. A Paradigm for Robust Geometric Algorithms, Cornell University Technical Report TR 89-1044, October 1989.

Digital Library

Google Scholar

[12]

Michael Karasick. On the Representation and Manipulation of Rigid Solids, PhD thesis, McGill University, August 1988.

Digital Library

Google Scholar

[13]

Z. Li, V. Milenkovic. Constructing Strongly Convex Hulls using Exact or Rounded Arithmetic, Proceedings of the Sixth Symposium on Computational Geometry, pages 235-243, ACM, June 1990.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[15]

Victor Milenkovic. Verifiable implementations of geometric algorithms using finite precision arithmetic, Artificial Intelligence, 37:377-401, 1988.

Digital Library

Google Scholar

[16]

Victor J. Milenkovic. Verifiable Implementations of Geometric Algorithms using Finite Precision Arithmetic, Ph.D. Thesis, Carnegie-Mellon, 1988. Technical Report CMU-CS-88-168, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, July 1988.

Digital Library

Google Scholar

[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.

Google Scholar

[18]

K. Sugihara, M. Iri, Geometric Algorithms in Finite- Precision Arithmetic, Research Memorandum RMI 88- 10, University of Tokyo, September, 1988.

Google Scholar

[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.

Google Scholar

Cited By

View all

Martynov VZakieva EPetunin A(2019)Modeling the Initial Shape in the Tasks of Automating the Design of Electronic Means Placement on a Flat Material2019 International Seminar on Electron Devices Design and Production (SED)10.1109/SED.2019.8798437(1-8)Online publication date: Apr-2019
https://doi.org/10.1109/SED.2019.8798437
Beichl IBernal JWitzgall CSullivan F(2016)Computational GeometryEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_142(241-246)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_142
Dumitriu DFunke SKutz MMilosavljević N(2010)How much geometry it takes to reconstruct a 2-manifold in R3ACM Journal of Experimental Algorithmics10.1145/1498698.153759714(2.2-2.17)Online publication date: 5-Jan-2010
https://dl.acm.org/doi/10.1145/1498698.1537597
Show More Cited By

Index Terms

Numerical stability of algorithms for line arrangements
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Stability analysis of numerical methods for systems of neutral delay-differential equations
Abstract
Stability analysis of some representative numerical methods for systems of neutral delay-differential equations (NDDEs) is considered. After the establishment of a sufficient condition of asymptotic stability for linear NDDEs, the stability ...
Global asymptotic stability and robust stability of a class of Cohen-Grossberg neural networks with mixed delays

This paper is concerned with the global asymptotic stability of a class of Cohen-Grossberg neural networks with both multiple time-varying delays and continuously distributed delays. Two classes of amplification functions are considered, and some ...
A numerical method for the stability analysis of quasi-polynomial vector fields
Theory and methods

This paper shows the sufficient conditions for the existence of a Lyapunov function in the class of quasi-polynomial dynamical systems. We focus on the cases where the system's parameters are numerically specified. A numerical algorithm to analyze this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '91: Proceedings of the seventh annual symposium on Computational geometry

June 1991

373 pages

ISBN:0897914260

DOI:10.1145/109648

Chairman:
R. L. Scot Drysdale

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOCG91

Sponsor:

SOCG91: 7th Annual Symposium on Computational Geometry 1991

June 10 - 12, 1991

New Hampshire, North Conway, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)13

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Martynov VZakieva EPetunin A(2019)Modeling the Initial Shape in the Tasks of Automating the Design of Electronic Means Placement on a Flat Material2019 International Seminar on Electron Devices Design and Production (SED)10.1109/SED.2019.8798437(1-8)Online publication date: Apr-2019
https://doi.org/10.1109/SED.2019.8798437
Beichl IBernal JWitzgall CSullivan F(2016)Computational GeometryEncyclopedia of Operations Research and Management Science10.1007/978-1-4419-1153-7_142(241-246)Online publication date: 23-Jan-2016
https://doi.org/10.1007/978-1-4419-1153-7_142
Dumitriu DFunke SKutz MMilosavljević N(2010)How much geometry it takes to reconstruct a 2-manifold in R3ACM Journal of Experimental Algorithmics10.1145/1498698.153759714(2.2-2.17)Online publication date: 5-Jan-2010
https://dl.acm.org/doi/10.1145/1498698.1537597
Graf TVeezhinathan K(2006)An optimal algorithm for computing visible nearest foreign neighbors among colored line segmentsAlgorithm Theory — SWAT'9810.1007/BFb0054355(59-70)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054355
Guibas L(2005)Implementing geometric algorithms robustlyApplied Computational Geometry Towards Geometric Engineering10.1007/BFb0014477(15-22)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014477
Schirra S(2005)Precision and robustness in geometric computationsAlgorithmic Foundations of Geographic Information Systems10.1007/3-540-63818-0_9(255-287)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-63818-0_9
Beichl IBernal JWitzgall CSullivan F(2005)Computational geometryEncyclopedia of Operations Research and Management Science10.1007/1-4020-0611-X_142(122-126)Online publication date: 25-Oct-2005
https://doi.org/10.1007/1-4020-0611-X_142
Halperin DLeiserowitz EFortune S(2003)Controlled perturbation for arrangements of circlesProceedings of the nineteenth annual symposium on Computational geometry10.1145/777792.777832(264-273)Online publication date: 8-Jun-2003
https://dl.acm.org/doi/10.1145/777792.777832
Mehlhorn K(2001)From Algorithm to Program to Software LibraryInformatics10.1007/3-540-44577-3_19(268-273)Online publication date: 29-Mar-2001
https://doi.org/10.1007/3-540-44577-3_19
Mukherjee MDaherkar AVattipalli R(2000)Satisfying coplanarity constraints on points sets in three dimensions with finite precision arithmeticComputer-Aided Design10.1016/S0010-4485(00)00055-532:11(663-679)Online publication date: Sep-2000
https://doi.org/10.1016/S0010-4485(00)00055-5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Stability analysis of numerical methods for systems of neutral delay-differential equations

Global asymptotic stability and robust stability of a class of Cohen-Grossberg neural networks with mixed delays

A numerical method for the stability analysis of quasi-polynomial vector fields