Constructive root bound for k-ary rational input numbers

Sylvain Pion; Chee K. Yap

Constructive root bound for k-ary rational input numbers

Computer Science

Research output: Contribution to conference › Paper › peer-review

Abstract

Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the presense of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since majority of input numbers in scientific and engineering applications are such numbers, this could lead to a significant speedup for a large class of applications. We apply our method to the BFMSS Bound. Implementation and experimental results based on the Core Library are reported.

Original language	English (US)
Pages	256-263
Number of pages	8
State	Published - 2003
Event	Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003

Other

Other	Nineteenth Annual Symposium on Computational Geometry
Country/Territory	United States
City	san Diego, CA
Period	6/8/03 → 6/10/03

Keywords

Constructive root bounds
Exact geometric computation
Robust numerical algorithms
k-ary rational numbers

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Cite this

@conference{5462b0861439447ab4b3cc77ba2621a6,

title = "Constructive root bound for k-ary rational input numbers",

abstract = "Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the presense of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since majority of input numbers in scientific and engineering applications are such numbers, this could lead to a significant speedup for a large class of applications. We apply our method to the BFMSS Bound. Implementation and experimental results based on the Core Library are reported.",

keywords = "Constructive root bounds, Exact geometric computation, Robust numerical algorithms, k-ary rational numbers",

author = "Sylvain Pion and Yap, {Chee K.}",

note = "Funding Information: This research is supported by NSF/ITR Grant #CCR-0082056. Sylvain{\textquoteright}s work is conducted under a postdoc fellowship with this grant. ∗ Corresponding author. Tel.: +33 492385025; fax: +33 492387683. E-mail addresses: [email protected] (S. Pion), [email protected] (C.K. Yap).; Nineteenth Annual Symposium on Computational Geometry ; Conference date: 08-06-2003 Through 10-06-2003",

year = "2003",

language = "English (US)",

pages = "256--263",

}

TY - CONF

T1 - Constructive root bound for k-ary rational input numbers

AU - Pion, Sylvain

AU - Yap, Chee K.

N1 - Funding Information: This research is supported by NSF/ITR Grant #CCR-0082056. Sylvain’s work is conducted under a postdoc fellowship with this grant. ∗ Corresponding author. Tel.: +33 492385025; fax: +33 492387683. E-mail addresses: [email protected] (S. Pion), [email protected] (C.K. Yap).

PY - 2003

Y1 - 2003

N2 - Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the presense of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since majority of input numbers in scientific and engineering applications are such numbers, this could lead to a significant speedup for a large class of applications. We apply our method to the BFMSS Bound. Implementation and experimental results based on the Core Library are reported.

AB - Constructive root bounds is the fundamental technique needed to achieve guaranteed accuracy, the critical capability in Exact Geometric Computation. Known bounds are overly pessimistic in the presense of general rational input numbers. In this paper, we introduce a method which greatly improves the known bounds for k-ary rational input numbers. Since majority of input numbers in scientific and engineering applications are such numbers, this could lead to a significant speedup for a large class of applications. We apply our method to the BFMSS Bound. Implementation and experimental results based on the Core Library are reported.

KW - Constructive root bounds

KW - Exact geometric computation

KW - Robust numerical algorithms

KW - k-ary rational numbers

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

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

M3 - Paper

AN - SCOPUS:0038714749

SP - 256

EP - 263

T2 - Nineteenth Annual Symposium on Computational Geometry

Y2 - 8 June 2003 through 10 June 2003

ER -

Constructive root bound for k-ary rational input numbers

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this