Computing minimum length paths of a given homotopy class (Q1330462): Difference between revisions

Revision as of 15:57, 22 May 2024

scientific article

Language	Label	Description	Also known as
English	Computing minimum length paths of a given homotopy class	scientific article

Statements

instance of

scholarly article

0 references

title

Computing minimum length paths of a given homotopy class (English)

0 references

published in

Computational Geometry

0 references

publication date

21 July 1994

0 references

review text

It is shown how the notion of the universal covering space of a triangulated region can be used as a unifying framework to compute paths under various metrics in a simple polygon. Shortest paths and shortest closed curves under Euclidean and link metrics and paths that are restricted to use \(c\) given orientations are considered and new algorithms for computing minimum length and minimum link \(c\)-oriented paths are given. Also algorithms using simple arrays and stacks instead of more complicated data structures used in previously known algorithms for Euclidean shortest path trees and minimum-link paths are given.

@@ Property / cites work @@
+Finding minimal convex nested polygons
@@ Property / cites work: Finding minimal convex nested polygons / rank @@
+Normal rank
@@ Property / cites work @@
+Q3876692
@@ Property / cites work: Q3876692 / rank @@
+Normal rank
@@ Property / cites work @@
+An Introduction to the Geometry of Numbers
@@ Property / cites work: An Introduction to the Geometry of Numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Triangulating a simple polygon in linear time
@@ Property / cites work: Triangulating a simple polygon in linear time / rank @@
+Normal rank
@@ Property / cites work @@
+Q3138983
@@ Property / cites work: Q3138983 / rank @@
+Normal rank
@@ Property / cites work @@
+Translating polygons with applications to hidden surface removal
+Normal rank
@@ Property / cites work @@
+On rectilinear link distance
@@ Property / cites work: On rectilinear link distance / rank @@
+Normal rank
@@ Property / cites work @@
+Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
+Normal rank
@@ Property / cites work @@
+Rectilinear shortest paths in the presence of rectangular barriers
+Normal rank
@@ Property / cites work @@
+A note on two problems in connexion with graphs
@@ Property / cites work: A note on two problems in connexion with graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Triangulating Simple Polygons and Equivalent Problems
+Normal rank
@@ Property / cites work @@
+Computing the visibility polygon from a convex set and related problems
+Normal rank
@@ Property / cites work @@
+An optimal algorithm for computing a minimum nested nonconvex polygon
+Normal rank
@@ Property / cites work @@
+An Output-Sensitive Algorithm for Computing Visibility Graphs
+Normal rank
@@ Property / cites work @@
+An efficient algorithm for determining the convex hull of a finite planar set
+Normal rank
@@ Property / cites work @@
+Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
+Normal rank
@@ Property / cites work @@
+Primitives for the manipulation of general subdivisions and the computation of Voronoi
+Normal rank
@@ Property / cites work @@
+Optimal shortest path queries in a simple polygon
@@ Property / cites work: Optimal shortest path queries in a simple polygon / rank @@
+Normal rank
@@ Property / cites work @@
+Q4134602
@@ Property / cites work: Q4134602 / rank @@
+Normal rank
@@ Property / cites work @@
+New algorithms for special cases of the hidden line elimination problem
+Normal rank
@@ Property / cites work @@
+Finding minimum rectilinear distance paths in the presence of barriers
+Normal rank
@@ Property / cites work @@
+Euclidean shortest paths in the presence of rectilinear barriers
+Normal rank
@@ Property / cites work @@
+Optimal Placement for River Routing
@@ Property / cites work: Optimal Placement for River Routing / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228431
@@ Property / cites work: Q4228431 / rank @@
+Normal rank
@@ Property / cites work @@
+The Number of Shortest Paths on the Surface of a Polyhedron
+Normal rank
@@ Property / cites work @@
+Q4064159
@@ Property / cites work: Q4064159 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2753135
@@ Property / cites work: Q2753135 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3992847
@@ Property / cites work: Q3992847 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal computation of finitely oriented convex hulls
+Normal rank
@@ Property / cites work @@
+Complexity of Single-Layer Routing
@@ Property / cites work: Complexity of Single-Layer Routing / rank @@
+Normal rank
@@ Property / cites work @@
+On Shortest Paths in Polyhedral Spaces
@@ Property / cites work: On Shortest Paths in Polyhedral Spaces / rank @@
+Normal rank
@@ Property / cites work @@
+A linear time algorithm for minimum link paths inside a simple polygon
+Normal rank
@@ Property / cites work @@
+The intersection searching problem for c-oriented polygons
+Normal rank
@@ Property / cites work @@
+On separating two simple polygons by a single translation
+Normal rank
@@ Property / cites work @@
+Q3716330
@@ Property / cites work: Q3716330 / rank @@
+Normal rank
@@ Property / cites work @@
+Finding minimal nested polygons
@@ Property / cites work: Finding minimal nested polygons / rank @@
+Normal rank

Computing minimum length paths of a given homotopy class (Q1330462): Difference between revisions

Revision as of 15:57, 22 May 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)