2026-08-18T17:38:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7214 2024-03-06T10:39:56Z ddc:004 open_access

Range-Clustering Queries Abrahamsen, Mikkel de Berg, Mark Buchin, Kevin Mehr, Mehran Mehrabi, Ali D. Geometric data structures clustering k-center problem In a geometric k-clustering problem the goal is to partition a set of points in R^d into k subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set S: given a query box Q and an integer k > 2, compute an optimal k-clustering for the subset of S inside Q. We obtain the following results. * We present a general method to compute a (1+epsilon)-approximation to a range-clustering query, where epsilon>0 is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric and a variant of k-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. * We extend our method to deal with capacitated k-clustering problems, where each of the clusters should not contain more than a given number of points. * For the special cases of rectilinear k-center clustering in R^1, and in R^2 for k = 2 or 3, we present data structures that answer range-clustering queries exactly. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and Mark de Berg and Kevin Buchin and Mehran Mehr and Ali D. Mehrabi 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.5 urn:nbn:de:0030-drops-72147 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.5 eng https://creativecommons.org/licenses/by/3.0/legalcode