DOI

  • Elena Arseneva
  • Man Kwun Chiu
  • Matias Korman
  • Aleksandar Markovic
  • Yoshio Okamoto
  • Aurélien Ooms
  • André Van Renssen
  • Marcel Roeloffzen

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(nω, n2 + nhlog h + χ2)) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω(n) ∩ O(n2) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n2 log n) time.

Язык оригиналаанглийский
Название основной публикации29th International Symposium on Algorithms and Computation, ISAAC 2018
РедакторыChung-Shou Liao, Wen-Lian Hsu, Der-Tsai Lee
ИздательSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Страницы58:1-58:13
ISBN (электронное издание)9783959770941
DOI
СостояниеОпубликовано - 1 дек 2018
Событие29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Китайская Провинция Тайвань
Продолжительность: 16 дек 201819 дек 2018

Серия публикаций

НазваниеLeibniz International Proceedings in Informatics, LIPIcs
Том123
ISSN (печатное издание)1868-8969

конференция

конференция29th International Symposium on Algorithms and Computation, ISAAC 2018
Страна/TерриторияКитайская Провинция Тайвань
ГородJiaoxi, Yilan
Период16/12/1819/12/18

    Предметные области Scopus

  • Программный продукт

ID: 48856835