| Autor: |
Chaeyoon Chung, Antoine Vigneron, Hee-Kap Ahn |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Symmetry, Vol 16, Iss 2, p 206 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2073-8994 |
| DOI: |
10.3390/sym16020206 |
| Popis: |
Given a set of n disks in the plane, we study the problem of finding k lines that together intersect the maximum number of input disks. We consider three variants of this problem with the following constraints on the solution: (1) no constraint on the lines, (2) the k lines should be parallel and (3) the k lines should pass through a common point. For k=2, we give O(n3logn)-time algorithms for all three cases. For any fixed k≥3, we give an O(n3k/2)-time algorithm for (1). For variants (2) and (3), the running times of our algorithms vary from O(n4) to O(n6). |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
