2026-07-23T20:44:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8775 2024-03-06T10:42:37Z ddc:004 open_access

Approximate Range Queries for Clustering Oh, Eunjin Ahn, Hee-Kap Approximate clustering orthogonal range queries We study the approximate range searching for three variants of the clustering problem with a set P of n points in d-dimensional Euclidean space and axis-parallel rectangular range queries: the k-median, k-means, and k-center range-clustering query problems. We present data structures and query algorithms that compute (1+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh and Hee-Kap Ahn 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.62 urn:nbn:de:0030-drops-87755 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.62 eng https://creativecommons.org/licenses/by/3.0/legalcode