8 papers
Geometric compression for progressive transmission
Olivier Devillers, Pierre-Maris Gandoin
The compression of geometric structures is a relatively new field of data compression. Since about 1995, several articles have dealt with the coding of meshes, using for most of th…
Finding an ordinary conic and an ordinary hyperplane
Olivier Devillers, Asish Mukhopadhyay
Given a finite set of non-collinear points in the plane, there exists a line that passes through exactly two points. Such a line is called an ordinary line. An efficient algorithm…
Convex Tours of Bounded Curvature
Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers +2
We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a co…
A Probabilistic Analysis of the Power of Arithmetic Filters
Olivier Devillers, Franco P. Preparata
The assumption of real-number arithmetic, which is at the basis of conventional geometric algorithms, has been seriously challenged in recent years, since digital computers do not…
Further Results on Arithmetic Filters for Geometric Predicates
Olivier Devillers, Franco P. Preparata
An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided…
The union of unit balls has quadratic complexity, even if they all contain the origin
Herve Bronnimann, Olivier Devillers
We provide a lower bound construction showing that the union of unit balls in three-dimensional space has quadratic complexity, even if they all contain the origin. This settles a…