Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon

DOI10.1007/S00453-011-9603-5MaRDI QIDQ2392920zbMATH OpenOpenAlexFDO

Authors Alfredo García, Pedro Jodrá, Javier Tejel

Publication date 5 August 2013

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9603-5

zbMATH Keywords

computational complexitydynamic programmingcomputational geometryHamiltonian pathMonge arraysimple polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Finding a shortest Hamiltonian path inside a simple polygon
• Computing a shortest watchman path in a simple polygon in polynomial-time
• An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane

Cites work

• scientific article; zbMATH DE number 432798 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• A Monge property for the \(d\)-dimensional transportation problem
• A linear-time algorithm for concave one-dimensional dynamic programming
• A new data structure for shortest path queries in a simple polygon
• A note on the traveling repairman problem
• A pricing problem under Monge property
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
• Finding a shortest Hamiltonian path inside a simple polygon
• Geometric applications of a matrix-searching algorithm
• Improved Algorithms for Economic Lot Size Problems
• Monge properties, discrete convexity and applications
• Monge strikes again: Optimal placement of web proxies in the internet
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Online dynamic programming speedups
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• Optimal shortest path queries in a simple polygon
• Parallel searching in generalized Monge arrays
• Perspectives of Monge properties in optimization
• Recognition of \(d\)-dimensional Monge arrays
• Speeding up dynamic programming with applications to molecular biology
• Traveling salesman games with the Monge property

Cited in

(2)

• Finding a shortest Hamiltonian path inside a simple polygon
• An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays

This page was built for publication: Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon

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