License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.58
URN: urn:nbn:de:0030-drops-100060
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10006/
Go to the corresponding LIPIcs Volume Portal

Arseneva, Elena ; Chiu, Man-Kwun ; Korman, Matias ; Markovic, Aleksandar ; Okamoto, Yoshio ; Ooms, Aurélien ; van Renssen, André ; Roeloffzen, Marcel

Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

pdf-format:
LIPIcs-ISAAC-2018-58.pdf (0.4 MB)

Abstract

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^omega, n^2 + nh log h + chi^2)) time, where omega<2.373 denotes the matrix multiplication exponent and chi in Omega(n) cap O(n^2) 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(n^2 log n) time.

BibTeX - Entry

@InProceedings{arseneva_et_al:LIPIcs:2018:10006,
  author =	{Elena Arseneva and Man-Kwun Chiu and Matias Korman and Aleksandar Markovic and Yoshio Okamoto and Aur{\'e}lien Ooms and Andr{\'e} van Renssen and Marcel Roeloffzen},
  title =	{{Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10006},
  URN =		{urn:nbn:de:0030-drops-100060},
  doi =		{10.4230/LIPIcs.ISAAC.2018.58},
  annote =	{Keywords: Rectilinear link distance, polygonal domain, diameter, radius}
}

Keywords: Rectilinear link distance, polygonal domain, diameter, radius
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI