On the Problem of Covering a 3-D Terrain

Eduard Eiben, Isuru S. Godage, Iyad Kanj, Ge Xia

AAAI 2020 pp. 10361-10368

doi:10.1609/AAAI.V34I06.6603 /aaai/2020/eiben2020aaai-problem/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Eiben et al. "On the Problem of Covering a 3-D Terrain." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I06.6603

Markdown

[Eiben et al. "On the Problem of Covering a 3-D Terrain." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/eiben2020aaai-problem/) doi:10.1609/AAAI.V34I06.6603

BibTeX

@inproceedings{eiben2020aaai-problem,
  title     = {{On the Problem of Covering a 3-D Terrain}},
  author    = {Eiben, Eduard and Godage, Isuru S. and Kanj, Iyad and Xia, Ge},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {10361-10368},
  doi       = {10.1609/AAAI.V34I06.6603},
  url       = {https://mlanthology.org/aaai/2020/eiben2020aaai-problem/}
}