Adaptive and efficient algorithm for 2D orientation problem

Katsuhisa Ozaki*, Takeshi Ogita, Siegfried M. Rump, Shin'ichi Oishi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


This paper is concerned with a robust geometric predicate for the 2D orientation problem. Recently, a fast and accurate floating-point summation algorithm is investigated by Rump, Ogita and Oishi, which provably outputs a result faithfully rounded from the exact value of the summation of floating-point numbers. We optimize their algorithm for applying it to the 2D orientation problem which requires only a correct sign of a determinant of a 3×3 matrix. Numerical results illustrate that our algorithm works fairly faster than the state-of-the-art algorithm in various cases.

Original languageEnglish
Pages (from-to)215-231
Number of pages17
JournalJapan Journal of Industrial and Applied Mathematics
Issue number2-3
Publication statusPublished - 2009 Oct


  • 2D orientation problem
  • Accurate algorithm
  • Floating-point arithmetic
  • Robust geometric predicate

ASJC Scopus subject areas

  • General Engineering
  • Applied Mathematics


Dive into the research topics of 'Adaptive and efficient algorithm for 2D orientation problem'. Together they form a unique fingerprint.

Cite this