Max-Min 3-Dispersion Problems

• HORIYAMA Takashi

  Hokkaido University

• NAKANO Shin-ichi

  Gunma University

• SAITOH Toshiki

  Kyushu Institute of Technology

• SUETSUGU Koki

  National Institute of Informatics

• SUZUKI Akira

  Tohoku University

• UEHARA Ryuhei

  JAIST

• UNO Takeaki

  National Institute of Informatics

• WASA Kunihiro

  Toyohashi University of Technology

抄録

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 L₁ metric. Also, we give an O(n² log n) time algorithm to solve the 3-dispersion problem in the L₂ metric.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E104.A (9), 1101-1107, 2021-09-01

  一般社団法人 電子情報通信学会

キーワード

• algorithms
• dispersion problem
• facility location

詳細情報

• CRID: 1390852182144621440
• NII論文ID: 130008081864
• DOI: 10.1587/transfun.2020dmp0003
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E104.A/9/E104.A_2020DMP0003/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可