검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position An O(n2)-볼록 위치의 점 세트에서 최대-최소 3-분산을 계산하기 위한 시간 알고리즘

Yasuaki KOBAYASHI, Shin-ichi NAKANO, Kei UCHIZAWA, Takeaki UNO, Yutaro YAMAGUCHI, Katsuhisa YAMANAKA

  • 조회수

    0

  • 이것을 인용

요약 :

세트가 주어지면 P of n 포인트와 정수 k, 우리는 배치하고 싶습니다 k 포인트 시설 P 시설간 최소거리를 극대화하였습니다. 문제는 k- 분산 문제, 그리고 그러한 세트 k 포인트라고 불리는 k-의 분산 P. 2-분산 문제는 다음의 직경 계산에 해당합니다. P. 그래서 k- 분산 문제는 직경 문제의 자연스러운 일반화입니다. 본 논문에서는 다음의 경우를 고려한다. k=3, 이는 3-분산 문제입니다. P 볼록한 위치에 있습니다. 우리는 O(n2)-시간 알고리즘으로 3-분산을 계산합니다. P.

발행
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.503-507
발행일
2022/03/01
공개일
2021/11/01
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2021FCP0013
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
범주

작성자

Yasuaki KOBAYASHI
  Kyoto University
Shin-ichi NAKANO
  Gunma University
Kei UCHIZAWA
  Yamagata University
Takeaki UNO
  National Institute of Informatics
Yutaro YAMAGUCHI
  Osaka University
Katsuhisa YAMANAKA
  Iwate University

키워드