TY - GEN
T1 - Algorithms for k-Dispersion for Points in Convex Position in the Plane
AU - Singireddy, Vishwanath R.
AU - Basappa, Manjanna
AU - Mitchell, Joseph S.B.
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - In this paper, we consider the following k-dispersion problem. Given a set S of n points placed in the plane in convex position and an integer k (0 < k< n ), the objective is to compute a subset S′⊂ S such that | S′| = k and the minimum distance between a pair of points in S′ is maximized. Based on the bounded search tree method, we propose an exact fixed-parameter algorithm in O(2 kn2log 2n) time for this problem, where k is the parameter. The proposed exact algorithm improves on the algorithm of Akagi et al. (2018), which requires time nO(k), whenever k< clog 2n for some constant c. We then give an exact polynomial-time (O(n4k2) ) algorithm, for any k> 0, thus answering the open question about the complexity of this restricted dispersion problem. For k= 3, there is an O(n2) -time algorithm by Kobayashi et al. (2021).
AB - In this paper, we consider the following k-dispersion problem. Given a set S of n points placed in the plane in convex position and an integer k (0 < k< n ), the objective is to compute a subset S′⊂ S such that | S′| = k and the minimum distance between a pair of points in S′ is maximized. Based on the bounded search tree method, we propose an exact fixed-parameter algorithm in O(2 kn2log 2n) time for this problem, where k is the parameter. The proposed exact algorithm improves on the algorithm of Akagi et al. (2018), which requires time nO(k), whenever k< clog 2n for some constant c. We then give an exact polynomial-time (O(n4k2) ) algorithm, for any k> 0, thus answering the open question about the complexity of this restricted dispersion problem. For k= 3, there is an O(n2) -time algorithm by Kobayashi et al. (2021).
KW - Delaunay triangulation
KW - Dynamic programming
KW - Fixed parameter tractable
KW - Max-min dispersion
KW - Obnoxious facility location
UR - https://www.scopus.com/pages/publications/85149822511
U2 - 10.1007/978-3-031-25211-2_5
DO - 10.1007/978-3-031-25211-2_5
M3 - Conference contribution
AN - SCOPUS:85149822511
SN - 9783031252105
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 59
EP - 70
BT - Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings
A2 - Bagchi, Amitabha
A2 - Muthu, Rahul
PB - Springer Science and Business Media Deutschland GmbH
T2 - 9th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2023
Y2 - 9 February 2023 through 11 February 2023
ER -