Maximum Independent Sets in Disk Graphs with Disks in Convex Position
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913025256062976 |
|---|---|
| author | Tkachenko, Anastasiia Wang, Haitao |
| author_facet | Tkachenko, Anastasiia Wang, Haitao |
| contents | For a set $\mathcal{D}$ of disks in the plane, its disk graph $G(\mathcal{D})$ is the graph with vertex set $\mathcal{D}$, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set $\mathcal{D}$ of $n$ weighted disks, computing a maximum independent set of $G(\mathcal{D})$ is NP-hard. In this paper, we present an $O(n^3\log n)$-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of $\mathcal{D}$. This setting has been studied previously for disks of equal radius, for which an $O(n^{37/11})$-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an $O(n^3\log^2 n)$-time algorithm for the dispersion problem on a set of $n$ disks in convex position: given an integer $k$, compute a subset of $k$ disks that maximizes the minimum pairwise distance among all disks in the subset. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10828 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximum Independent Sets in Disk Graphs with Disks in Convex Position Tkachenko, Anastasiia Wang, Haitao Computational Geometry Data Structures and Algorithms For a set $\mathcal{D}$ of disks in the plane, its disk graph $G(\mathcal{D})$ is the graph with vertex set $\mathcal{D}$, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set $\mathcal{D}$ of $n$ weighted disks, computing a maximum independent set of $G(\mathcal{D})$ is NP-hard. In this paper, we present an $O(n^3\log n)$-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of $\mathcal{D}$. This setting has been studied previously for disks of equal radius, for which an $O(n^{37/11})$-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an $O(n^3\log^2 n)$-time algorithm for the dispersion problem on a set of $n$ disks in convex position: given an integer $k$, compute a subset of $k$ disks that maximizes the minimum pairwise distance among all disks in the subset. |
| title | Maximum Independent Sets in Disk Graphs with Disks in Convex Position |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.10828 |