Recent progress in exact geometric computation

C. Li; S. Pion; C. K. Yap

doi:10.1016/j.jlap.2004.07.006

Recent progress in exact geometric computation

C. Li, S. Pion, C. K. Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving numerical non-robustness, Exact Geometric Computation (EGC) has emerged as one of the most successful. This survey describes recent progress in EGC research in three key areas: constructive zero bounds, approximate expression evaluation and numerical filters.

Original language	English (US)
Pages (from-to)	85-111
Number of pages	27
Journal	Journal of Logic and Algebraic Programming
Volume	64
Issue number	1
DOIs	https://doi.org/10.1016/j.jlap.2004.07.006
State	Published - Jul 2005

Keywords

Approximate expression evaluation
C++ libraries
Constructive zero bounds
Exact geometric computation
Interval arithmetic
Non-robustness problems
Numerical filters
Precision-driven computation
Robust algorithms

ASJC Scopus subject areas

Software
Theoretical Computer Science
Logic
Computational Theory and Mathematics

Access to Document

10.1016/j.jlap.2004.07.006

Cite this

@article{82b908093e814bd0854092a5158f3396,

title = "Recent progress in exact geometric computation",

abstract = "Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving numerical non-robustness, Exact Geometric Computation (EGC) has emerged as one of the most successful. This survey describes recent progress in EGC research in three key areas: constructive zero bounds, approximate expression evaluation and numerical filters.",

keywords = "Approximate expression evaluation, C++ libraries, Constructive zero bounds, Exact geometric computation, Interval arithmetic, Non-robustness problems, Numerical filters, Precision-driven computation, Robust algorithms",

author = "C. Li and S. Pion and Yap, {C. K.}",

note = "Funding Information: This paper is based on a talk presented at the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, March 12–16, 2001. The work is supported by NSF/ITR Grant #CCR-0082056 and by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No. IST-2000-26473 (ECG––Effective Computational Geometry for Curves and Surfaces). ∗ Corresponding author. E-mail addresses: chenli@cs.nyu.edu (C. Li), sylvain.pion@sophia.inria.fr (S. Pion), yap@cs.nyu.edu (C.K. Yap).",

year = "2005",

month = jul,

doi = "10.1016/j.jlap.2004.07.006",

language = "English (US)",

volume = "64",

pages = "85--111",

journal = "Journal of Logic Programming",

issn = "1567-8326",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Recent progress in exact geometric computation

AU - Li, C.

AU - Pion, S.

AU - Yap, C. K.

N1 - Funding Information: This paper is based on a talk presented at the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, March 12–16, 2001. The work is supported by NSF/ITR Grant #CCR-0082056 and by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No. IST-2000-26473 (ECG––Effective Computational Geometry for Curves and Surfaces). ∗ Corresponding author. E-mail addresses: chenli@cs.nyu.edu (C. Li), sylvain.pion@sophia.inria.fr (S. Pion), yap@cs.nyu.edu (C.K. Yap).

PY - 2005/7

Y1 - 2005/7

N2 - Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving numerical non-robustness, Exact Geometric Computation (EGC) has emerged as one of the most successful. This survey describes recent progress in EGC research in three key areas: constructive zero bounds, approximate expression evaluation and numerical filters.

AB - Computational geometry has produced an impressive wealth of efficient algorithms. The robust implementation of these algorithms remains a major issue. Among the many proposed approaches for solving numerical non-robustness, Exact Geometric Computation (EGC) has emerged as one of the most successful. This survey describes recent progress in EGC research in three key areas: constructive zero bounds, approximate expression evaluation and numerical filters.

KW - Approximate expression evaluation

KW - C++ libraries

KW - Constructive zero bounds

KW - Exact geometric computation

KW - Interval arithmetic

KW - Non-robustness problems

KW - Numerical filters

KW - Precision-driven computation

KW - Robust algorithms

UR - http://www.scopus.com/inward/record.url?scp=17644422204&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17644422204&partnerID=8YFLogxK

U2 - 10.1016/j.jlap.2004.07.006

DO - 10.1016/j.jlap.2004.07.006

M3 - Article

AN - SCOPUS:17644422204

VL - 64

SP - 85

EP - 111

JO - Journal of Logic Programming

JF - Journal of Logic Programming

SN - 1567-8326

IS - 1

ER -

Recent progress in exact geometric computation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this