Elias' Article

The predicates for the Voronoi diagram of ellipses.
Ioannis Z. Emiris, Elias P. Tsigaridas, and George Tzoumas.
In Proc. 22nd Annual ACM Symp. Comput. Geom. (SoCG), pp. 227–236, ACM, Sedona, Arizona, USA, June 5-7 2006.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 273.4kB  [gzipped postscript] 358.3kB  

Abstract:

This paper examines the computation of the Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete algorithms, under the exact computation paradigm, for the predicates of an incremental algorithm: \ka decides which one of 2 given ellipses is closest to a given exterior point; \kb decides the position of a query ellipse relative to an external bitangent line of 2 given ellipses; \kc decides the position of a query ellipse relative to a Voronoi circle of 3 given ellipses; \kd determines the type of conflict between a Voronoi edge, defined by 4 given ellipses, and a query ellipse. The paper is restricted to non-intersecting ellipses, but the extension to arbitrary ones is straightforward. The ellipses are input in parametric representation or constructively in terms of their axes, center and rotation. For \ka and \kb we derive optimal algebraic conditions, solve them exactly and provide efficient implementations in C++. For \kc we compute a tight bound on the number of complex tritangent circles and use the parametric form of the ellipses in order to design an exact subdivision-based algorithm, which is implemented on Maple. This approach essentially answers \kd as well. We conclude with current work on optimizing \kc and implementing it in C++.

@InProceedings{ett-socg-2006,
  author =       {Ioannis~Z. Emiris and Elias~P. Tsigaridas and George
                  Tzoumas},
  title =        {{The predicates for the Voronoi diagram of
                  ellipses}},
  booktitle =    SOCG_2006,
  pages =        {227--236},
  year =         2006,
  editor =       {N. Amenta and O. Cheong},
  address =      {Sedona, Arizona, USA},
  month =        {June 5-7},
  publisher =    {ACM},
  abstract =     " This paper examines the computation of the Voronoi
                  diagram of a set of ellipses in the Euclidean plane.
                  We propose the first complete algorithms, under the
                  exact computation paradigm, for the predicates of an
                  incremental algorithm: \ka{} decides which one of 2
                  given ellipses is closest to a given exterior point;
                  \kb{} decides the position of a query ellipse
                  relative to an external bitangent line of 2 given
                  ellipses; \kc{} decides the position of a query
                  ellipse relative to a Voronoi circle of 3 given
                  ellipses; \kd{} determines the type of conflict
                  between a Voronoi edge, defined by 4 given ellipses,
                  and a query ellipse.  The paper is restricted to
                  non-intersecting ellipses, but the extension to
                  arbitrary ones is straightforward.  The ellipses are
                  input in parametric representation or constructively
                  in terms of their axes, center and rotation.  For
                  \ka{} and \kb{} we derive optimal algebraic
                  conditions, solve them exactly and provide efficient
                  implementations in C++.  For \kc{} we compute a
                  tight bound on the number of complex tritangent
                  circles and use the parametric form of the ellipses
                  in order to design an exact subdivision-based
                  algorithm, which is implemented on Maple.  This
                  approach essentially answers \kd{} as well.  We
                  conclude with current work on optimizing \kc{} and
                  implementing it in C++.  ",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02