Range-clustering queries

DOI10.4230/LIPICS.SOCG.2017.5zbMATH Open1432.68478arXiv1705.06242OpenAlexW2615714319MaRDI QIDQ4580076FDOQ4580076

Authors: Mikkel Abrahamsen, Kevin Buchin, Mehran Mehr, Ali D. Mehrabi, Mark de Berg 

Publication date: 13 August 2018

Abstract: In a geometric $k$-clustering problem the goal is to partition a set of points in $mathbb{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 $SsetminusQ$. 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 $L_p$-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 $mathbb{R}^1$, and in $mathbb{R}^2$ for $k=2$ or 3, we present data structures that answer range-clustering queries exactly.

Full work available at URL: https://arxiv.org/abs/1705.06242

Recommendations

• Approximate range queries for clustering
• Exact and approximation algorithms for clustering
• scientific article; zbMATH DE number 1303609
• On approximate geometric \(k\)-clustering
• Approximation schemes for clustering problems

zbMATH Keywords

clusteringgeometric data structures\(k\)-center problem

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (8)

• Preclustering Algorithms for Imprecise Points
• STACS 2005
• Window queries for intersecting objects, maximal points and approximations using coresets
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency
• Range-Aggregate Queries Involving Geometric Aggregation Operations
• Approximate range queries for clustering
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Balanced compact clustering for efficient range queries in metric spaces

This page was built for publication: Range-clustering queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580076)