We consider the problem of finding a minimalistic configuration of sensors that enable a simple robot inside an initially unknown polygon PP on nn vertices to reconstruct the visibility graph of PP. The robot can sense features of its environment through its sensors, and it is allowed to move from vertex to vertex. We aim at understanding which sensorial capabilities are sufficient for the reconstruction of the visibility graph of PP. We are able to show that the combinatorial visibilities at every vertex do not contain enough information even when combined with the knowledge of the exact interior angle at each vertex. Using sensors that can put distant vertices into a spatial relation on the other hand can in some cases enable our robot to reconstruct the visibility graph of PP. We show that this is true for a sensor that can distinguish whether the angle between the lines toward two visible vertices is convex or reflex, as long as the robot is capable of identifying the vertex it last visited. We also show that measuring angles exactly is enough, if the robot has a compass.

Reconstructing visibility graphs with simple robots / Bilò, Davide; Disser, Yann; Mihalak, Matus; Suri, Subash; Vicari, Elias; Widmayer, Peter. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 444:(2012), pp. 52-59. [10.1016/j.tcs.2012.01.008]

Reconstructing visibility graphs with simple robots

BILÒ, Davide;
2012-01-01

Abstract

We consider the problem of finding a minimalistic configuration of sensors that enable a simple robot inside an initially unknown polygon PP on nn vertices to reconstruct the visibility graph of PP. The robot can sense features of its environment through its sensors, and it is allowed to move from vertex to vertex. We aim at understanding which sensorial capabilities are sufficient for the reconstruction of the visibility graph of PP. We are able to show that the combinatorial visibilities at every vertex do not contain enough information even when combined with the knowledge of the exact interior angle at each vertex. Using sensors that can put distant vertices into a spatial relation on the other hand can in some cases enable our robot to reconstruct the visibility graph of PP. We show that this is true for a sensor that can distinguish whether the angle between the lines toward two visible vertices is convex or reflex, as long as the robot is capable of identifying the vertex it last visited. We also show that measuring angles exactly is enough, if the robot has a compass.
2012
Reconstructing visibility graphs with simple robots / Bilò, Davide; Disser, Yann; Mihalak, Matus; Suri, Subash; Vicari, Elias; Widmayer, Peter. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 444:(2012), pp. 52-59. [10.1016/j.tcs.2012.01.008]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11388/80721
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact