|
 
Innumerable scientific and engineering applications from geology to
telecommunications lead to the same problem: given a set of objects, find which object
is nearest to any particular point. The Voronoi diagram answers this question
for every point on the plane by dividing the plane into cells containing
the points nearest each object. Because this question arises in
so many applications, highly efficient algorithms and codes
for computing Voronoi diagrams have been developed in the case the objects are
idealized as simple points. I. Emiris and E. Tsigaridas
of the National University of Athens visited the IMA during the 2006-2007
program on Algebraic Geometry and focused on the problem of extending
efficient algorithms for computing exact Voronoi diagrams to the case of more
general objects which can be described algebraically, such as ellipses.
The hardest module to extend was something called the InCircle predicate,
which decides the relative position of a query ellipse with respect to a
circle externally tangent to three other ellipses. Emiris, Tsigarides, and Ph.D. student G. Tzoumas
reduced this query to calculations on algebraic numbers of degree 184.
To make these calculations rapidly, they figured out an approach combining
certified numerical algorithms with algebraic computations.
The work of Emiris, Tsigarides, and Tzoumas provides the first complete
implementation for the exact computation of the Voronoi diagram
of ellipses. It is targeted for inclusion in the open source
computational geometry library, CGAL,
and so will join the toolbox available to mathematicians and scientists.
Related material
- Voronoi diagram of ellipses, the project
website
- I. Emiris and G. Tzoumas, The
Voronoi circle of smooth closed curves, poster for an IMA meeting 2007
- I. Emiris and G. Tzoumas,
A
real-time and exact implementation of the predicates for the
Voronoi diagram of parametric ellipses,
in SPM'07,
Beijing, China, June 2007
- I. Emiris, E. Tsigaridas, and G. Tzoumas,
The
predicates for the Voronoi diagram of ellipses,
in SoCG'06,
Sedona,
Arizona, June 2006
|
