Simple floating-point filters for the two-dimensional orientation problem

Katsuhisa Ozaki; Florian Bünger; Takeshi Ogita; Shin’ichi Oishi; Siegfried M. Rump

doi:10.1007/s10543-015-0574-9

Simple floating-point filters for the two-dimensional orientation problem

Katsuhisa Ozaki^*, Florian Bünger, Takeshi Ogita, Shin’ichi Oishi, Siegfried M. Rump

^*Corresponding author for this work

School of Fundamental Science and Engineering

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

5 Citations (Scopus)

Abstract

This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-point arithmetic, then an incorrect result may be obtained due to accumulation of rounding errors. A floating-point filter can quickly guarantee the correctness of the computed result if the problem is well-conditioned. In this paper, a simple semi-static floating-point filter which handles floating-point exceptions such as overflow and underflow by only one branch is developed. In addition, an improved fully-static filter is developed.

Original language	English
Pages (from-to)	729-749
Number of pages	21
Journal	BIT Numerical Mathematics
Volume	56
Issue number	2
DOIs	https://doi.org/10.1007/s10543-015-0574-9
Publication status	Published - 2016 Jun 1

Keywords

Computational geometry
Floating-point arithmetic
Floating-point filter

ASJC Scopus subject areas

Software
Computer Networks and Communications
Computational Mathematics
Applied Mathematics

Access to Document

10.1007/s10543-015-0574-9

Cite this

@article{f37ba6a3bb4b4a028385b91b8ec8ef66,

title = "Simple floating-point filters for the two-dimensional orientation problem",

abstract = "This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-point arithmetic, then an incorrect result may be obtained due to accumulation of rounding errors. A floating-point filter can quickly guarantee the correctness of the computed result if the problem is well-conditioned. In this paper, a simple semi-static floating-point filter which handles floating-point exceptions such as overflow and underflow by only one branch is developed. In addition, an improved fully-static filter is developed.",

keywords = "Computational geometry, Floating-point arithmetic, Floating-point filter",

author = "Katsuhisa Ozaki and Florian B{\"u}nger and Takeshi Ogita and Shin{\textquoteright}ichi Oishi and Rump, {Siegfried M.}",

note = "Funding Information: The authors wishes to thank the anonymous referee for constructive and valuable comments. This research was partially supported by the CREST program, Japan Science and Technology Agency (JST). Publisher Copyright: {\textcopyright} 2015, Springer Science+Business Media Dordrecht.",

year = "2016",

month = jun,

day = "1",

doi = "10.1007/s10543-015-0574-9",

language = "English",

volume = "56",

pages = "729--749",

journal = "BIT",

issn = "0006-3835",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Simple floating-point filters for the two-dimensional orientation problem

AU - Ozaki, Katsuhisa

AU - Bünger, Florian

AU - Ogita, Takeshi

AU - Oishi, Shin’ichi

AU - Rump, Siegfried M.

N1 - Funding Information: The authors wishes to thank the anonymous referee for constructive and valuable comments. This research was partially supported by the CREST program, Japan Science and Technology Agency (JST). Publisher Copyright: © 2015, Springer Science+Business Media Dordrecht.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-point arithmetic, then an incorrect result may be obtained due to accumulation of rounding errors. A floating-point filter can quickly guarantee the correctness of the computed result if the problem is well-conditioned. In this paper, a simple semi-static floating-point filter which handles floating-point exceptions such as overflow and underflow by only one branch is developed. In addition, an improved fully-static filter is developed.

AB - This paper is concerned with floating-point filters for a two dimensional orientation problem which is a basic problem in the field of computational geometry. If this problem is only approximately solved by floating-point arithmetic, then an incorrect result may be obtained due to accumulation of rounding errors. A floating-point filter can quickly guarantee the correctness of the computed result if the problem is well-conditioned. In this paper, a simple semi-static floating-point filter which handles floating-point exceptions such as overflow and underflow by only one branch is developed. In addition, an improved fully-static filter is developed.

KW - Computational geometry

KW - Floating-point arithmetic

KW - Floating-point filter

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

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

U2 - 10.1007/s10543-015-0574-9

DO - 10.1007/s10543-015-0574-9

M3 - Article

AN - SCOPUS:84937882728

SN - 0006-3835

VL - 56

SP - 729

EP - 749

JO - BIT

JF - BIT

IS - 2

ER -

Simple floating-point filters for the two-dimensional orientation problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this