NUK - logo
E-resources
Full text
Peer reviewed Open access
  • Dispersion in a Polygon
    ARAKI, Tetsuya; NAKANO, Shin-ichi

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2024, 2024-00-00
    Journal Article

    The dispersion problem is a variant of facility location problems, that has been extensively studied. Given a polygon with n edges on a plane we want to find k points in the polygon so that the minimum pairwise Euclidean distance of the k points is maximized. We call the problem the k-dispersion problem in a polygon. Intuitively, for an island, we want to locate k drone bases far away from each other in flying distance to avoid congestion in the sky. In this paper, we give a polynomial-time approximation scheme (PTAS) for this problem when k is a constant and ε < 1 (where ε is a positive real number). Our proposed algorithm runs in O(((1/ε)2 + n/ε)k) time with 1/(1 + ε) approximation, the first PTAS developed for this problem. Additionally, we consider three variations of the dispersion problem and design a PTAS for each of them.