On Some Distance Problems in Fixed Orientations

DOI10.1137/0216049zbMATH Open0625.68049OpenAlexW2146919520MaRDI QIDQ3028355FDOQ3028355

Authors:

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216049

zbMATH Keywords

minimum spanning treecomputational geometryconvex polygonsVoronoi diagramVLSI designplanar distance problems

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Cited In (37)

• The Steiner tree problem in orientation metrics
• Generalized halfspaces in restricted-orientation convexity
• Tropical bisectors and Voronoi diagrams
• Optimal curvature-constrained paths for general directional-cost functions
• Robust Point-Location in Generalized Voronoi Diagrams
• Steiner trees for fixed orientation metrics
• Minimum-link paths revisited
• An algorithmic approach to some problems in terrain navigation
• Shortest paths among transient obstacles
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Computing \(L_1\) shortest paths among polygonal obstacles in the plane
• Rotationally optimal spanning and Steiner trees in uniform orientation metrics
• PLANAR STRONG VISIBILITY
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• A methodology for modelling travel distances by bias estimation
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• Locally minimal uniformly oriented shortest networks
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• Fundamentals of restricted-orientation convexity
• Applications of a numbering scheme for polygonal obstacles in the plane
• Steiner minimal trees in rectilinear and octilinear planes
• Optimization on directionally convex sets
• On graphs preserving rectilinear shortest paths in the presence of obstacles
• The geometry of Minkowski spaces -- a survey. II.
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• Angle-restricted tours in the plane.
• Rectilinear paths among rectilinear obstacles
• A single facility stochastic location problem under A-distance
• Parallel rectilinear shortest paths with rectangular obstacles
• Robustness of \(k\)-gon Voronoi diagram construction
• Planar location problems with block distance and barriers
• Fastest-path planning for direction-dependent speed functions
• On the \(\mathcal{O}_\beta\)-hull of a planar point set
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• Forbidden subpaths for Steiner minimum networks in uniform orientation metrics
• Proximity problems for points on a rectilinear plane with rectangular obstacles
• On geometric path query problems

This page was built for publication: On Some Distance Problems in Fixed Orientations

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