More Web Proxy on the site http://driver.im/

Article

Free access

Calculating approximate curve arrangements using rounded arithmetic

Author:

V. MilenkovicAuthors Info & Claims

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

Pages 197 - 207

https://doi.org/10.1145/73833.73856

Published: 05 June 1989 Publication History

Abstract

We present here an algorithm for the curve arrangement problem: determine how a set of planar curves subdivides the plane. This algorithm uses rounded arithmetic and generates an approximate result. It can be applied to a broad class of planar curves, and it is based on a new definition of approximate curve arrangements. This result is an important step towards the creation of practical computer programs for reasoning about algebraic curves of high degree.

References

[1]

D. S. Arnon, G. E. Collins, and S. McCallum. An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. J. Symbolic Computation, 5:163-187, 1988.

Digital Library

[2]

D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical algebraic decompositions i: the basic algorithm. SIAM J. Comp., 13(4):865-877, 1984.

Digital Library

[3]

D. S. Arnon, G. E. Collins, and S. McCallum. Cylindrical algebraic decompositions ii: an adjacency algorithm for the plane. SIAM J. Comp., 13(4):878-889, 1984.

Digital Library

[4]

G. E. Collins. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Lecture Notes in Computer Science, No. 85, Springer-Verlag, New York, 1975.

[5]

M. Cost and M. F. Roy. Thorn's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. J. Symbolic Computation, 5:121-129, 1988.

Digital Library

[6]

Herbert Edelsbrunner and Ernst Peter Mucke. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms. Technical Report UIUCDCS-R-87-1393, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois, December 1987.

[7]

Daniel H. Greene and F. Frances Yao. Finiteresolution computational geometry. In 27th Annual Symposium on the Foundations of Computer Science, pages 143-152, IEEE, October 1986.

[8]

C. Hoffmann and J. Hopcroft. Towards implementing robust geometric computations. In Proceedings of the Symposium on Computational Geometry, ACM, 1988.

Digital Library

[9]

Christoph M. Hoffmann. The Problem of Accuracy and Robustness in Geometric Computation. Technical Report CSD-TR-771, Computer Sciences Department, Purdue University, April 1988.

[10]

Christoph M. Hoffmann, John E. Hopcroft, and Michael S. Karasick. Robust Set Operations on Polyhedral Solids. Technical Report 87-875, Department of Computer Science, Cornell University, Ithaca, New York 14853-7501, October 1987.

Digital Library

[11]

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

Digital Library

[12]

M. Karsick, D. Lieber, and L. Nackman. Ejficient Delaunay Triangulation using Rational Arithmetic. IBM Research Report RC 14455, IBM Thomas J. Watson Research,Center, P.O. Box 218, Yorktown Heights, NY 10598, To appear in 1989.

[13]

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

Digital Library

[14]

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

Digital Library

[15]

Thomas Ottmann, Gerald Thiemt, and Christian Ullrich. Numerical stability of geometric algorithms. In Proceedings of the Symposium on Computational Geometry, ACM, 1987.

Digital Library

[16]

M. 0. Rabin. Probabilistic algorithms in finite fields. SIAM J. Comp., 9(2):273-280, May 1980.

[17]

D. Salesin, J. Stolfi, and L. Guibas. Epsilon geometry: building robust algorithms from imprecise computations. In Proceedings of the Symposium on Computational Geometry, ACM, 1989.

Digital Library

[18]

J. Schwartz and M. Sharir. On the 'piano movers' problem, ii. general techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math., 4:298-301, 1983.

Digital Library

[19]

Mark Segal and Carlo H. Sequin. Consistent calculations for solids modeling. In Proceedings of the Symposium on Computational Geometry, pages 29-37, ACM, June 1985.

Digital Library

[20]

Mark Segal and Carlo H. Sequin. Partitioning polyhedral objects into non-intersecting parts. IEEE Computer Graphics and Applications, 8(l), January 1988.

Digital Library

[21]

K. Sugihara. An approach to error-free solid modeling. In IMA Summer Program on Robotics, Institute for Mathematics and Applications, University of Minnesota, 1987.

[22]

A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1948. 2nd edition, 1951.

[23]

C. Yap. A geometric consistency theorem for a symbolic perturbation theorem. In Proceedings of the Symposium on Computational Geometry, ACM, 1988.

Digital Library

Cited By

Guibas LSalesin DStolfi J(2005)Constructing strongly convex approximate hulls with inaccurate primitivesAlgorithms10.1007/3-540-52921-7_75(261-270)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52921-7_75
Chen WWada KKawaguchi K(2002)Robust algorithms for constructing strongly convex hulls in parallelTheoretical Computer Science10.1016/S0304-3975(01)00274-2289:1(277-295)Online publication date: 23-Oct-2002
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900274-2
Neagu M(2000)Polygonal Approximations for Curved Problems: An Application to ArrangementsDiscrete and Computational Geometry10.1007/978-3-540-46515-7_20(235-249)Online publication date: 2000
https://doi.org/10.1007/978-3-540-46515-7_20
Show More Cited By

Index Terms

Calculating approximate curve arrangements using rounded arithmetic
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Planar G² transition with a fair Pythagorean hodograph quintic curve

Recently planar cubic and Pythagorean hodograph quintic transition curves that are suitable for G² blending were developed. They are suitable for blending, e.g. rounding corners, or for smooth transition between two curves, e.g. two circular arcs. It ...
Approximating Rational Bézier Curve with Polynomial Curve Using Re-parameterization
IFCSTA '09: Proceedings of the 2009 International Forum on Computer Science-Technology and Applications - Volume 02

The problem of approximating rational curves by polynomial curves is studied in this paper. A simple method of approximation, which uses the control points of the degree-elevated curve to approximate the original rational curve, is introduced at first. ...
A simple method for approximating rational Bézier curve using Bézier curves

This paper presents a simple method for approximating a rational Bezier curve with Bezier curve sequence, whose control points are those of degree-elevated rational Bezier curves. It is proved that the derivatives with any given degree of the Bezier ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

June 1989

401 pages

ISBN:0897913183

DOI:10.1145/73833

Chairman:
Kurt Mehlhorn

Copyright © 1989 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
313
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guibas LSalesin DStolfi J(2005)Constructing strongly convex approximate hulls with inaccurate primitivesAlgorithms10.1007/3-540-52921-7_75(261-270)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52921-7_75
Chen WWada KKawaguchi K(2002)Robust algorithms for constructing strongly convex hulls in parallelTheoretical Computer Science10.1016/S0304-3975(01)00274-2289:1(277-295)Online publication date: 23-Oct-2002
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900274-2
Neagu M(2000)Polygonal Approximations for Curved Problems: An Application to ArrangementsDiscrete and Computational Geometry10.1007/978-3-540-46515-7_20(235-249)Online publication date: 2000
https://doi.org/10.1007/978-3-540-46515-7_20
Agarwal PSuri S(1996)Simple and practical geometric algorithmsACM Computing Surveys10.1145/242224.24224428:4es(16-es)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1145/242224.242244
Kahan SSnoeyink JWhitesides S(1996)On the bit complexity of minimum link pathsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237342(151-158)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237342
Chen WWada KKawaguchi KWhitesides S(1996)Parallel robust algorithms for constructing strongly convex hullsProceedings of the twelfth annual symposium on Computational geometry10.1145/237218.237329(133-140)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/237218.237329
Matias YVitter JYoung NSleator D(1994)Approximate data structures with applicationsProceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/314464.314493(187-194)Online publication date: 23-Jan-1994
https://dl.acm.org/doi/10.5555/314464.314493
Guibas LSalesin DStolfi J(1993)Constructing strongly convex approximate hulls with inaccurate primitivesAlgorithmica10.1007/BF011901549:6(534-560)Online publication date: Jun-1993
https://doi.org/10.1007/BF01190154
Li ZMilenkovic VSeidel R(1990)Constructing strongly convex hulls using exact or rounded arithmeticProceedings of the sixth annual symposium on Computational geometry10.1145/98524.98577(235-243)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/98524.98577
Segal M(1990)Using tolerances to guarantee valid polyhedral modeling resultsACM SIGGRAPH Computer Graphics10.1145/97880.9789124:4(105-114)Online publication date: 1-Sep-1990
https://dl.acm.org/doi/10.1145/97880.97891
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents