publication . Conference object . Article . 2009

general predicates, and implementation for ellipses

Ioannis Emiris; Elias Tsigaridas; George Tzoumas;
Restricted
  • Published: 05 Oct 2009
  • Publisher: ACM Press
Abstract
We examine the problem of computing exactly the Delaunay graph (and the dual Voronoi diagram) of a set of, possibly intersecting, smooth convex pseudo-circles in the Euclidean plane, given in parametric form. Pseudo-circles are (convex) sites, every pair of which has at most two intersecting points. The Delaunay graph is constructed incrementally. Our first contribution is to propose robust end efficient algorithms for all required predicates, thus generalizing our earlier algorithms for ellipses, and we analyze their algebraic complexity, under the exact computation paradigm. Second, we focus on InCircle, which is the hardest predicate, and express it by a simp...
Subjects
arXiv: Computer Science::Computational Geometry
ACM Computing Classification System: TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYMathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Polynomial, Bowyer–Watson algorithm, Euclidean geometry, Computer science, Regular polygon, Ellipse, Constrained Delaunay triangulation, Discrete mathematics, Voronoi diagram, Mathematical optimization, Combinatorics, Incircle and excircles of a triangle
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue