| Title: |
Clustering with Few Disks to Minimize the Sum of Radii |
| Authors: |
Abrahamsen, Mikkel; de Berg, Sarita; Meijer, Lucas; Nusser, André; Theocharous, Leonidas; Sub Geometric Computing; Sub Algorithms and Complexity; Geometric Computing; Mulzer, Wolfgang; Phillips, Jeff M. |
| Publication Year: |
2024 |
| Subject Terms: |
covering points with disks; geometric clustering; minimize sum of radii; Software |
| Description: |
Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV’12]; however, the running time of this algorithm is O(n881), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time O(n2 log2 n log2 log n) was given over 30 years ago [Eppstein’92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected O(n log2 n log2 log n) time. We generalize this result to any constant dimension d, for which we give an O(n2−1/(⌈d/2⌉+1)+ε) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected O(n2 log2 n log2 log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482307 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482307 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.3F12C4D2 |
| Database: |
BASE |