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

DOI10.1007/S00453-011-9603-5zbMATH Open1310.68204OpenAlexW2040958164MaRDI QIDQ2392920FDOQ2392920

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

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

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)

Cites Work

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

Cited In (2)

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

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)