Maximum Centre-Disjoint Mergeable Disks
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915920716234752 |
|---|---|
| author | Rudi, Ali Gholami |
| author_facet | Rudi, Ali Gholami |
| contents | Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_04350 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Maximum Centre-Disjoint Mergeable Disks Rudi, Ali Gholami Computational Geometry 68u05 F.2.2 Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line. |
| title | Maximum Centre-Disjoint Mergeable Disks |
| topic | Computational Geometry 68u05 F.2.2 |
| url | https://arxiv.org/abs/2301.04350 |