On the Problem of Covering a 3-D Terrain

Autor:	Eduard Eiben, Ge Xia, Isuru S. Godage, Iyad A. Kanj
Rok vydání:	2020
Předmět:	symbols.namesake Computer science Heuristic symbols Graph (abstract data type) Terrain General Medicine Algorithm Polynomial-time approximation scheme Graph MathematicsofComputing_DISCRETEMATHEMATICS Planar graph
Zdroj:	AAAI
ISSN:	2374-3468 2159-5399
Popis:	We study the problem of covering a 3-dimensional terrain by a sweeping robot that is equipped with a camera. We model the terrain as a mesh in a way that captures the elevation levels of the terrain; this enables a graph-theoretic formulation of the problem in which the underlying graph is a weighted plane graph. We show that the associated graph problem is NP-hard, and that it admits a polynomial time approximation scheme (PTAS). Finally, we implement two heuristic algorithms based on greedy approaches and report our findings.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2196bc399c8467b7e4f2abd251de9807 https://doi.org/10.1609/aaai.v34i06.6603 Zobrazit plný text záznamu