{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:33:30Z","timestamp":1760708010051},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p> This article examines the computation of the Delaunay graph and its dual 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: \u03ba<jats:sub>1<\/jats:sub> decides which one of two given ellipses is closest to a given exterior point; \u03ba<jats:sub>2<\/jats:sub> decides the position of a query ellipse relative to an external bitangent line of two given ellipses; \u03ba<jats:sub>3<\/jats:sub> decides the position of a query ellipse relative to a Voronoi circle of three given ellipses; \u03ba<jats:sub>4<\/jats:sub> 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. <\/jats:p><jats:p> The ellipses are input in parametric representation, i.e., constructively in terms of their axes, center and rotation. For \u03ba<jats:sub>1<\/jats:sub> and \u03ba<jats:sub>2<\/jats:sub> we derive algebraic conditions optimal in terms of the degree of the algebraic numbers involved, and provide efficient implementations in C++ . For \u03ba<jats:sub>3<\/jats:sub> 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 \u03ba<jats:sub>4<\/jats:sub> as well. We conclude with further work on lifting the condition of non-intersecting ellipses. <\/jats:p>","DOI":"10.1142\/s0218195908002763","type":"journal-article","created":{"date-parts":[[2008,12,14]],"date-time":"2008-12-14T20:07:59Z","timestamp":1229285279000},"page":"567-597","source":"Crossref","is-referenced-by-count":4,"title":["THE PREDICATES FOR THE EXACT VORONOI DIAGRAM OF ELLIPSES UNDER THE EUCLIDIEAN METRIC"],"prefix":"10.1142","volume":"18","author":[{"given":"IOANNIS Z.","family":"EMIRIS","sequence":"first","affiliation":[{"name":"Department of Informatics and Telecommunications, National Kapodistrian University of Athens, 15784 Panepistimiopolis, Athens, Hellas"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELIAS P.","family":"TSIGARIDAS","sequence":"additional","affiliation":[{"name":"INRIA-LORIA Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-l\u00e9s-Nancy cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GEORGE M.","family":"TZOUMAS","sequence":"additional","affiliation":[{"name":"Department of Informatics and Telecommunications, National Kapodistrian University of Athens, 15784 Panepistimiopolis, Athens, Hellas"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Effective Computational Geometry for Curves and Surfaces","author":"Boissonnat J.-D.","year":"2007"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90033-3"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.006"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716580"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1192-0"},{"key":"rf11","first-page":"563","volume":"18","author":"Kim D.-S.","journal-title":"CAGD"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2824-x"},{"key":"rf17","series-title":"GTM","volume-title":"Using Algebraic Geometry","volume":"185","author":"Cox D.","year":"2005"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(01)00049-8"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2006.01.002"},{"key":"rf23","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"Yap C. K.","year":"2000"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-3406-1_16"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195908002763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:16:29Z","timestamp":1565176589000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195908002763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":12,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1142\/S0218195908002763"],"URL":"https:\/\/doi.org\/10.1142\/s0218195908002763","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]}}}