Article

Free access

Robust adaptive floating-point geometric predicates

Author:

Johnathan Richard ShewchukAuthors Info & Claims

SCG '96: Proceedings of the twelfth annual symposium on Computational geometry

Pages 141 - 150

https://doi.org/10.1145/237218.237337

Published: 01 May 1996 Publication History

PDF eReader

References

[1]

Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, Franco P. Preparata, and Mariette Yvinec. Evaluating Signs of Determinants Using Single-Precision Arithmetic. 1995.

Google Scholar

[2]

David H. Bailey. A Portable High Performance Multiprecision Package. Technical Report RNR-90-022, NASA Ames Research Center, May 1993.

Google Scholar

[3]

Kenneth L. Clarkson. Safe and Effective Determinant Evaluation. 33rd Annual Symposium on Foundations of Computer Science, pages 387-395, 1992.

Google Scholar

[4]

T.J. Dekker. A Floating-Point Technique for Extending the Available Precision. Numerische Mathematik 18:224-242, 1971.

Digital Library

Google Scholar

[5]

Steven Fortune and Christopher J. Van Wyk. Efficient Exact Arithmetic for Computational Geometry. Ninth Annual Symposium on Computational Geometry, pages 163-172, May 1993.

Digital Library

Google Scholar

[6]

Static Analysis Yields Efficient Exact Integer Arithmetic for Computational Geometry. To appear in Transactions on Mathematical Software, 1996.

Google Scholar

[7]

David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys 23(1):5-48, March 1991.

Digital Library

Google Scholar

[8]

Leonidas J. Guibas and Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics 4(2):74-I23, April 1985.

Digital Library

Google Scholar

[9]

Michael Karasick, Derek Lieber, and Lee R. Nackman. Efficient Delaunay Triangulation Using Rational Arithmetic. ACM Transactions on Graphics 10(1):71-91, January 1991.

Digital Library

Google Scholar

[10]

Donald Ervin Knuth. The Art of Computer Programming: Seminumerical Algorithms, second edition, volume 2. Addison Wesley, 1981.

Google Scholar

[11]

D. T. Lee and B. J. Schachter. Two Algorithms for Constructing a Delaunay Triangulation. Int. J. Comput. Inf. Sci. 9:219-242, 1980.

Crossref

Google Scholar

[12]

Douglas M. Priest. Algorithms for Arbitrary Precision Floating Point Arithmetic. Tenth Symposium on Computer Arithmetic, pages 132- I43, 1991.

Google Scholar

[13]

On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. Ph.D. thesis, Department of Mathematics, University of California at Berkeley, November 1992.

Google Scholar

[14]

Jonathan Richard Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. First Workshop on Applied Computational Geometry. Association for Computing Machinery, May 1996.

Digital Library

Google Scholar

[15]

David F. Watson. Computing the r~-dimenstonal Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal 24:167-172, 1981.

Crossref

Google Scholar

Cited By

View all

Ledoux H(2024)startinpy: A Python library for modelling and processing 2.5D triangulated terrainsJournal of Open Source Software10.21105/joss.071239:103(7123)Online publication date: Nov-2024
https://doi.org/10.21105/joss.07123
Green MKirilov KTurner MMarcon JEichstädt JLaughton ECantwell CSherwin SPeiró JMoxey D(2024)NekMesh: An open-source high-order mesh generation frameworkComputer Physics Communications10.1016/j.cpc.2024.109089(109089)Online publication date: Jan-2024
https://doi.org/10.1016/j.cpc.2024.109089
Lévy B(2022)Partial optimal transport for a constant-volume Lagrangian mesh with free boundariesJournal of Computational Physics10.1016/j.jcp.2021.110838451:COnline publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110838
Show More Cited By

Index Terms

Robust adaptive floating-point geometric predicates
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
  2. Mathematical analysis
    1. Numerical analysis
      1. Arbitrary-precision arithmetic
      2. Interval arithmetic
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Decimal Floating-Point Multiplication

Decimal multiplication is important in many commercial applications including financial analysis, banking, tax calculation, currency conversion, insurance, and accounting. This paper presents the design of two decimal floating-point multipliers: one ...
Hardware Designs for Decimal Floating-Point Addition and Related Operations

Decimal arithmetic is often used in commercial, financial, and Internet-based applications. Due to the growing importance of decimal floating-point (DFP) arithmetic, the IEEE 754 Draft Standard for Floating-Point Arithmetic (IEEE P754) includes ...
Fast decimal floating-point division

A new implementation for decimal floating-point (DFP) division is introduced. The algorithm is based on high-radix SRT division with the recurrence in a new decimal signed-digit format. Quotient digits are selected using comparison multiples, where the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '96: Proceedings of the twelfth annual symposium on Computational geometry

May 1996

406 pages

ISBN:0897918045

DOI:10.1145/237218

Chairman:
Sue Whitesides
McGill Univ.

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 May 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG96

Sponsor:

SoCG96: 12th ACM Symposium on Computational Geometry

May 24 - 26, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

SCG '96 Paper Acceptance Rate 48 of 93 submissions, 52%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
966
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ledoux H(2024)startinpy: A Python library for modelling and processing 2.5D triangulated terrainsJournal of Open Source Software10.21105/joss.071239:103(7123)Online publication date: Nov-2024
https://doi.org/10.21105/joss.07123
Green MKirilov KTurner MMarcon JEichstädt JLaughton ECantwell CSherwin SPeiró JMoxey D(2024)NekMesh: An open-source high-order mesh generation frameworkComputer Physics Communications10.1016/j.cpc.2024.109089(109089)Online publication date: Jan-2024
https://doi.org/10.1016/j.cpc.2024.109089
Lévy B(2022)Partial optimal transport for a constant-volume Lagrangian mesh with free boundariesJournal of Computational Physics10.1016/j.jcp.2021.110838451:COnline publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110838
Maňák MAnikeenko AVáša LKolingerová I(2022)Compact storage of additively weighted Voronoi diagramsThe Visual Computer10.1007/s00371-022-02667-z39:11(5389-5404)Online publication date: 12-Oct-2022
https://doi.org/10.1007/s00371-022-02667-z
Romanschek EClemen CHuhnt W(2021)A Novel Robust Approach for Computing DE-9IM Matrices Based on Space Partition and Integer CoordinatesISPRS International Journal of Geo-Information10.3390/ijgi1011071510:11(715)Online publication date: 20-Oct-2021
https://doi.org/10.3390/ijgi10110715
Damiand GCoeurjolly DBourquat P(2021)Stripped halfedge data structure for parallel computation of arrangements of segmentsThe Visual Computer10.1007/s00371-021-02185-4Online publication date: 16-Jun-2021
https://doi.org/10.1007/s00371-021-02185-4
Paoluzzi AShapiro VDicarlo AFuriani FMartella GScorzelli G(2020)Topological Computing of Arrangements with (Co)ChainsACM Transactions on Spatial Algorithms and Systems10.1145/34019887:1(1-29)Online publication date: 14-Oct-2020
https://dl.acm.org/doi/10.1145/3401988
Chitalu FMiao QSubr KKomura T(2020)Displacement‐Correlated XFEM for Simulating Brittle FractureComputer Graphics Forum10.1111/cgf.1395339:2(569-583)Online publication date: 13-Jul-2020
https://doi.org/10.1111/cgf.13953
Hafner CSchumacher CKnoop EAuzinger TBickel BBächer M(2019)X-CADACM Transactions on Graphics10.1145/3355089.335657638:6(1-15)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3355089.3356576
Zou CMo HGao CDu RFu H(2019)Language-based colorization of scene sketchesACM Transactions on Graphics10.1145/3355089.335656138:6(1-16)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3355089.3356561
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

Decimal Floating-Point Multiplication

Hardware Designs for Decimal Floating-Point Addition and Related Operations

Fast decimal floating-point division