Rectilinear link diameter and radius in a rectilinear polygonal domain

DOI10.1016/J.COMGEO.2020.101685MaRDI QIDQ827313zbMATH OpenOpenAlexFDO

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

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.05538

zbMATH Keywords

diameterradiuspolygonal domainrectilinear link distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

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 emph{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 $min,O(n^{o}mega),O(n^2+nhlogh+ch{i}^2),$ time, where $omega<2.373$ denotes the matrix multiplication exponent and $chiinOmega(n)capO(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^{2}logn)$ time.

Recommendations

• scientific article; zbMATH DE number 176583
• An optimal algorithm for the rectilinear link center of a rectilinear polygon
• On rectilinear link distance
• Computing the L 1-diameter and center of a simple rectilinear polygon in parallel
• The geodesic diameter of polygonal domains

Cites work

• scientific article; zbMATH DE number 6707504 (Why is no real title available?)
• scientific article; zbMATH DE number 176583 (Why is no real title available?)
• scientific article; zbMATH DE number 7030514 (Why is no real title available?)
• A linear-time algorithm for the geodesic center of a simple polygon
• All-pairs shortest paths in geometric intersection graphs
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• An optimal algorithm for the rectilinear link center of a rectilinear polygon
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Computing geodesic furthest neighbors in simple polygons
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Matrix Searching with the Shortest-Path Metric
• Minimum-link paths revisited
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Powers of tensors and fast matrix multiplication
• The geodesic diameter of polygonal domains
• \(L_ 1\) shortest paths among polygonal obstacles in the plane

Cited in

(3)

• Rectilinear link diameter and radius in a rectilinear polygonal domain
• Settling the bound on the rectilinear link radius of a simple rectilinear polygon
• scientific article; zbMATH DE number 176583 (Why is no real title available?)

This page was built for publication: Rectilinear link diameter and radius in a rectilinear polygonal domain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q827313)