Elias' Article

Predicates for the exact Voronoi diagram of ellipses under the Euclidean metric.
Ioannis Z. Emiris, Elias P. Tsigaridas, and George Tzoumas.
Int'l J. Comput. Geom. Appl., 18(6):567–597, 2008. (special issue devoted to SoCG 2007)

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 366.6kB  [gzipped postscript] 454.3kB  

Abstract:

This article examines the computation of the Voronoi diagram of a set of ellipses in the Euclidean plane. We propose the first complete methods, under the exact computation paradigm, for the predicates of an incremental algorithm: \ka decides which one of two given ellipses is closest to a given exterior point; \kb decides the position of a query ellipse relative to an external bitangent line of two given ellipses; \kc decides the position of a query ellipse relative to a Voronoi circle of three given ellipses; \kd determines the type of conflict between a Voronoi edge, defined by four given ellipses, and a query ellipse. The article is restricted to non-intersecting ellipses, but the extension to arbitrary ones is possible. The ellipses are input in parametric representation, i.e. constructively in terms of their axes, center and rotation. For \ka and \kb we derive optimal algebraic conditions and provide efficient implementations in \cpp. For \kc we compute a tight bound on the number of complex tritangent circles and design an exact symbolic-numeric algorithm, which is implemented in \maple. This essentially answers \kd as well. We conclude with current work on optimizing \kc and on its implementation in \cpp.

@Article{ett-ijcga-2007,
  author =       {Ioannis~Z. Emiris and Elias~P. Tsigaridas and George
                  Tzoumas},
  title =        {{Predicates for the exact Voronoi diagram of
                  ellipses under the Euclidean metric}},
  journal =      IJCGA,
  year =         2008,
  volume =       18,
  number =       6,
  pages =        "567--597",
  editor =       {N. Amenta and O. Cheong},
  note =         {(special issue devoted to SoCG 2007)},
  abstract =     " This article examines the computation of the
                  Voronoi diagram of a set of ellipses in the
                  Euclidean plane.  We propose the first complete
                  methods, under the exact computation paradigm, for
                  the predicates of an incremental algorithm: \ka
                  decides which one of two given ellipses is closest
                  to a given exterior point; \kb decides the position
                  of a query ellipse relative to an external bitangent
                  line of two given ellipses; \kc decides the position
                  of a query ellipse relative to a Voronoi circle of
                  three given ellipses; \kd determines the type of
                  conflict between a Voronoi edge, defined by four
                  given ellipses, and a query ellipse.  The article is
                  restricted to non-intersecting ellipses, but the
                  extension to arbitrary ones is possible.  The
                  ellipses are input in parametric representation,
                  i.e. constructively in terms of their axes, center
                  and rotation.  For \ka and \kb we derive optimal
                  algebraic conditions and provide efficient
                  implementations in \cpp.  For \kc we compute a tight
                  bound on the number of complex tritangent circles
                  and design an exact symbolic-numeric algorithm,
                  which is implemented in \maple.  This essentially
                  answers \kd as well.  We conclude with current work
                  on optimizing \kc and on its implementation in
                  \cpp.",
}

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