The search functionality is under construction.

Author Search Result

[Author] Koki SUETSUGU(1hit)

1-1hit
  • Max-Min 3-Dispersion Problems Open Access

    Takashi HORIYAMA  Shin-ichi NAKANO  Toshiki SAITOH  Koki SUETSUGU  Akira SUZUKI  Ryuhei UEHARA  Takeaki UNO  Kunihiro WASA  

     
    PAPER-Algorithms and Data Structures

      Pubricized:
    2021/03/19
      Vol:
    E104-A No:9
      Page(s):
    1101-1107

    Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.