Algorithms for k-Dispersion for Points in Convex Position in the Plane

Vishwanath R. Singireddy; Manjanna Basappa; Joseph S.B. Mitchell

doi:10.1007/978-3-031-25211-2_5

Algorithms for k-Dispersion for Points in Convex Position in the Plane

Vishwanath R. Singireddy
, Manjanna Basappa
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Birla Institute of Technology and Science Pilani

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

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 ^kn²log ²n) 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 ²n for some constant c. We then give an exact polynomial-time (O(n⁴k²) ) 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(n²) -time algorithm by Kobayashi et al. (2021).

Original language	English
Title of host publication	Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings
Editors	Amitabha Bagchi, Rahul Muthu
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	59-70
Number of pages	12
ISBN (Print)	9783031252105
DOIs	https://doi.org/10.1007/978-3-031-25211-2_5
State	Published - 2023
Event	9th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2023 - Gandhinagar, India Duration: Feb 9 2023 → Feb 11 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13947 LNCS

Conference

Conference	9th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2023
Country/Territory	India
City	Gandhinagar
Period	02/9/23 → 02/11/23

Keywords

Delaunay triangulation
Dynamic programming
Fixed parameter tractable
Max-min dispersion
Obnoxious facility location

Access to Document

10.1007/978-3-031-25211-2_5

Cite this

Singireddy, V. R., Basappa, M., & Mitchell, J. S. B. (2023). Algorithms for k-Dispersion for Points in Convex Position in the Plane. In A. Bagchi, & R. Muthu (Eds.), Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings (pp. 59-70). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13947 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-25211-2_5

Singireddy, Vishwanath R. ; Basappa, Manjanna ; Mitchell, Joseph S.B. / Algorithms for k-Dispersion for Points in Convex Position in the Plane. Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings. editor / Amitabha Bagchi ; Rahul Muthu. Springer Science and Business Media Deutschland GmbH, 2023. pp. 59-70 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{43ba8e50b82b4d6c952294816b0ad91d,

title = "Algorithms for k-Dispersion for Points in Convex Position in the Plane",

abstract = "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).",

keywords = "Delaunay triangulation, Dynamic programming, Fixed parameter tractable, Max-min dispersion, Obnoxious facility location",

author = "Singireddy, \{Vishwanath R.\} and Manjanna Basappa and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 9th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2023 ; Conference date: 09-02-2023 Through 11-02-2023",

year = "2023",

doi = "10.1007/978-3-031-25211-2\_5",

language = "English",

isbn = "9783031252105",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "59--70",

editor = "Amitabha Bagchi and Rahul Muthu",

booktitle = "Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings",

}

Singireddy, VR, Basappa, M & Mitchell, JSB 2023, Algorithms for k-Dispersion for Points in Convex Position in the Plane. in A Bagchi & R Muthu (eds), Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13947 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 59-70, 9th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2023, Gandhinagar, India, 02/9/23. https://doi.org/10.1007/978-3-031-25211-2_5

Algorithms for k-Dispersion for Points in Convex Position in the Plane. / Singireddy, Vishwanath R.; Basappa, Manjanna; Mitchell, Joseph S.B.
Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings. ed. / Amitabha Bagchi; Rahul Muthu. Springer Science and Business Media Deutschland GmbH, 2023. p. 59-70 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13947 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

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

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 -

Singireddy VR, Basappa M, Mitchell JSB. Algorithms for k-Dispersion for Points in Convex Position in the Plane. In Bagchi A, Muthu R, editors, Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 59-70. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-25211-2_5

Algorithms for k-Dispersion for Points in Convex Position in the Plane

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this