On rectilinear link distance

DOI10.1016/0925-7721(91)90010-CzbMath0731.68094OpenAlexW2113370909MaRDI QIDQ808302

Mark T. de Berg

Publication date: 1991

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(91)90010-c

zbMATH Keywords

rectilinear polygonmotion planninglink distancepolygon cutting theoremrectilinear paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (17)

Computing minimum length paths of a given homotopy class ⋮ Linear-size planar Manhattan network for convex point sets ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ On condorcet and median points of simple rectilinear polygons ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ Computing a maxian point of a simple rectilinear polygon ⋮ An optimal algorithm for the rectilinear link center of a rectilinear polygon ⋮ A multifacility location problem on median spaces ⋮ Settling the bound on the rectilinear link radius of a simple rectilinear polygon ⋮ Minimum-link paths revisited ⋮ GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane ⋮ Rectilinear paths among rectilinear obstacles ⋮ An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons ⋮ Computing a median point of a simple rectilinear polygon

Cites Work

• Unnamed Item
• Computing the link center of a simple polygon
• Rectilinear shortest paths in the presence of rectangular barriers
• Fast Algorithms for Finding Nearest Common Ancestors
• Optimal Point Location in a Monotone Subdivision
• Finding minimum rectilinear distance paths in the presence of barriers
• Optimal Search in Planar Subdivisions
• An O(n log n) algorithm for computing a link center in a simple polygon

This page was built for publication: On rectilinear link distance