Optimal parallel algorithms for rectilinear link-distance problems

DOI10.1007/BF01206332zbMath0831.68108OpenAlexW2043144539WikidataQ62037495 ScholiaQ62037495MaRDI QIDQ1897477

Andrzej Lingas, Anil Maheshwari, Jörg-Rüdiger Sack

Publication date: 27 August 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01206332

zbMATH Keywords

parallel random access machinelink-distance problemsoptimal parallel solutions

Mathematics Subject Classification ID

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

Related Items (6)

Computing the L 1-diameter and center of a simple rectilinear polygon in parallel ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ An optimal algorithm for the rectilinear link center of a rectilinear polygon ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ An \(O(n^{5/2}\log n)\) algorithm for the rectilinear minimum link-distance problem in three dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rectilinear link distance
• Computing the link center of a simple polygon
• Rectilinear shortest paths in the presence of rectangular barriers
• Triangulating a simple polygon in linear time
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Matching parentheses in parallel
• Computing geodesic furthest neighbors in simple polygons
• Optimal parallel algorithms for rectilinear link-distance problems
• An addendum to parallel methods for visibility and shortest-path problems in simple polygons
• A linear time algorithm for minimum link paths inside a simple polygon
• An Efficient Parallel Biconnectivity Algorithm
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• MANHATTONIAN PROXIMITY IN A SIMPLE POLYGON
• -Algorithms for Minimum Link Path and Related Problems
• Computing the visibility polygon from a convex set and related problems

This page was built for publication: Optimal parallel algorithms for rectilinear link-distance problems