An Improved Strategy for Exploring a Grid Polygon

DOI10.1007/978-3-642-11476-2_18zbMath1274.68570OpenAlexW1587145552MaRDI QIDQ3408174

Michał Małafiejski, Adrian Kosowski, Paweł Żyliński, Agnieszka Kolenderska

Publication date: 24 February 2010

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11476-2_18

zbMATH Keywords

competitive ratiopath planningmobile robotexploration problemgrid polygon

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

Related Items

Off-line exploration of rectangular cellular environments with a rectangular obstacle ⋮ Worst-case optimal exploration of terrains with obstacles ⋮ Fast collaborative graph exploration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Not being (super)thin or solid is hard: A study of grid Hamiltonicity
• Hamiltonian properties of triangular grid graphs
• Approximation algorithms for lawn mowing and milling
• Competitive on-line coverage of grid environments by a mobile robot
• Graph exploration by a finite automaton
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Undirected ST-connectivity in log-space
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Hamilton Paths in Grid Graphs
• Computing and Combinatorics