Rectilinear link diameter and radius in a rectilinear polygonal domain

DOI10.1016/J.COMGEO.2020.101685zbMATH Open1477.68457arXiv1712.05538OpenAlexW2963853266MaRDI QIDQ827313FDOQ827313

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)

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.

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

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

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)

Cites Work

• Powers of tensors and fast matrix multiplication
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Fast approximation algorithms for the diameter and radius of sparse graphs
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Minimum-link paths revisited
• The geodesic diameter of polygonal domains
• Matrix Searching with the Shortest-Path Metric
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Computing geodesic furthest neighbors in simple polygons
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• A linear-time algorithm for the geodesic center of a simple polygon
• 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
• Title not available (Why is that?)
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains
• Title not available (Why is that?)
• Title not available (Why is that?)
• All-pairs shortest paths in geometric intersection graphs

Cited In (2)

• Title not available (Why is that?)
• Settling the bound on the rectilinear link radius of a simple rectilinear polygon

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)