Rectilinear link diameter and radius in a rectilinear polygonal domain

Elena Arseneva, Man Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen (Corresponding author), Marcel Roeloffzen

Research output: Contribution to journalArticleAcademicpeer-review

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ω,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(n2log⁡n) time.

Original languageEnglish
Article number101685
Number of pages11
JournalComputational Geometry: Theory and Applications
Volume92
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Diameter
  • Polygonal domain
  • Radius
  • Rectilinear link distance

Fingerprint Dive into the research topics of 'Rectilinear link diameter and radius in a rectilinear polygonal domain'. Together they form a unique fingerprint.

Cite this