Published in

Proceedings of the sixteenth annual symposium on Computational geometry - SCG '00

DOI: 10.1145/336154.336194

Elsevier, Computational Geometry, 1-3(22), p. 119-142, 2002

DOI: 10.1016/s0925-7721(01)00050-5

Links

Tools

Export citation

Search in Google Scholar

Algebraic methods and arithmetic filtering for exact predicates on circle arcs

Journal article published in 2000 by Olivier Devillers ORCID, Alexandra Fronville, Bernard Mourrain, Monique Teillaud
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

The purpose of this paper is to present a new method to design exact geometric predicates in algorithms dealing with curved objects such as circular arcs. We focus on the comparison of the abscissae of two intersection points of circle arcs, which is known to be a difficult predicate involved in the computation of arrangements of circle arcs. We present an algorithm for deciding the x-order of intersections from the signs of the coefficients of a polynomial, obtained by a general approach based on resultants. This method allows the use of efficient arithmetic and filtering techniques leading to fast implementation as shown by the experimental results.  2001 Elsevier Science B.V. All rights reserved.