Document Open Access Logo

Range-Clustering Queries

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.5.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.5

Abstract

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.

Subject Classification

Keywords
  • Geometric data structures
  • clustering
  • k-center problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Abam, P. Carmi, M. Farshi, and M. Smid. On the power of the semi-separated pair decomposition. Compututational Geometry: Theory and Applications, 46:631-639, 2013. Google Scholar
  2. P. K. Agarwal, R. Ben Avraham, and M. Sharir. The 2-center problem in three dimensions. Compututational Geometry: Theory and Applications, 46:734-746, 2013. Google Scholar
  3. P. K. Agarwal and Cecilia M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33:201-226, 2002. Google Scholar
  4. Sunil Arya, David M. Mount, and Eunhui Park. Approximate geometric MST range queries. In Proc. 36th International Symposium on Computational Geometry (SoCG), pages 781-795, 2015. Google Scholar
  5. Peter Brass, Christian Knauer, Chan-Su Shin, Michiel H. M. Smid, and Ivo Vigan. Range-aggregate queries for geometric extent problems. In Computing: The Australasian Theory Symposium 2013, CATS'13, pages 3-10, 2013. Google Scholar
  6. V. Capoyleas, G. Rote, and G. Woeginger. Geometric clusterings. Journal of Algorithms, 12:341-356, 1991. Google Scholar
  7. T. M. Chan. Geometric applications of a randomized optimization technique. Discrete &Compututational Geometry, 22:547-567, 1999. Google Scholar
  8. T. M. Chan. More planar two-center algorithms. Compututational Geometry: Theory and Applications, 13:189-198, 1999. Google Scholar
  9. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17:427-462, 1988. Google Scholar
  10. A. W. Das, P. Gupta, K. Kothapalli, and K. Srinathan. On reporting the L₁-metric closest pair in a query rectangle. Information Processing Letters, 114:256-263, 2014. Google Scholar
  11. Mark de Berg, Marc van Kreveld, and Jack Snoeyink. Two- and three-dimensional point location in rectangular subdivisions. Journal of Algorithms, 18:256-277, 1995. Google Scholar
  12. D. Eppstein. Faster construction of planar two-centers. In Proc. 8th Annual ACM-SIAM Symposiun on Discrete Algorithms (SODA), pages 131-138, 1997. Google Scholar
  13. P. Gupta, R. Janardan, Y. Kumar, and M. Smid. Data structures for range-aggregate extent queries. Compututational Geometry: Theory and Applications, 47:329-347, 2014. Google Scholar
  14. Sariel Har-Peled. Geometric Approximation Algorithms, volume 173 of Mathematical surveys and monographs. American Mathematical Society, 2011. Google Scholar
  15. Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proc. 36th Annual ACM Symposium on Theory of Computing (STOC), pages 291-300, 2004. Google Scholar
  16. M. Hoffmann. A simple linear algorithm for computing rectilinear 3-centers. Compututational Geometry: Theory and Applications, 31:150-165, 2005. Google Scholar
  17. R. Z. Hwang, R. Lee, and R. C. Chang. The generalized searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica, 9:398-423, 1993. Google Scholar
  18. S. Khare, J. Agarwal, N. Moidu, and K. Srinathan. Improved bounds for smallest enclosing disk range queries. In Proc. 26th Canadian Conference on Computational Geometry (CCCG), 2014. Google Scholar
  19. H.-P. Lenhof and M. H. M. Smid. Using persistent data structures for adding range restrictions to searching problems. Theoretical Informatics and Applications, 28:25-49, 1994. Google Scholar
  20. Yakov Nekrich and Michiel H. M. Smid. Approximating range-aggregate queries using coresets. In Proc. 22nd Canadian Conference on Computational Geometry (CCCG), pages 253-256, 2010. Google Scholar
  21. Jeff M. Phillips. Algorithms for ε-approximations of terrains. In Proc. 35th International Colloquium on Automata, Languages, and Programming (ICALP), pages 447-458, 2008. Google Scholar
  22. M. Sharir. A near-linear time algorithm for the planar 2-center problem. Discrete &Compututational Geometry, 18:125-134, 1997. Google Scholar
  23. M. Sharir and E. Welzl. Rectilinear and polygonal p-piercing and p-center problems. In Proc. 12th International Symposium on Computational Geometry (SoCG), pages 122-132, 1996. Google Scholar
  24. Gelin Zhou. Two-dimensional range successor in optimal time and almost linear space. Information Processing Letters, 116:171-174, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact