2026-04-13T15:05:14Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/3409472026-02-07T09:05:22Zcom_2072_1033col_2072_452950

Farthest color Voronoi diagrams: complexity and algorithms Mantas, Ioannis Papadopoulou, Evanthia Sacristán Adinolfi, Vera Silveira, Rodrigo Ignacio Àrees temàtiques de la UPC::Matemàtiques i estadística::Estadística matemàtica::Anàlisi multivariant Multivariate analysis Farthest color · MaxMin · Voronoi diagram · Point clusters Anàlisi multivariable Classificació AMS::62 Statistics::62H Multivariate analysis The farthest-color Voronoi diagram (FCVD) is a farthestsite Voronoi structure defined on a family P of m point-clusters in the plane, where the total number of points is n. The FCVD finds applications in problems related to color spanning objects and facility location. We identify structural properties of the FCVD, refine its combinatorial complexity bounds, and list conditions under which the diagram has O(n) complexity. We show that the diagram may have complexity ¿(n + m2 ) even if clusters have disjoint convex hulls. We present construction algorithms with running times ranging from O(n log n), when certain conditions are met, to O((n+s(P)) log3 n) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in P (s(P) ¿ O(mn)). A pair of points q1, q2 ¿ Q is said to straddle p1, p2 ¿ P if the line segment q1q2 intersects (straddles) the line through p1, p2 and the disks through (p1, p2, q1) and (p1, p2, q2) contain no points of P, Q. The complexity of the diagram is shown to be O(n + s(P)). Peer Reviewed Postprint (author's final draft) 2021 Conference report https://link.springer.com/chapter/10.1007%2F978-3-030-61792-9_23 info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT Restricted access - publisher's policy Springer