Publication details

On the Topology of Walkable Environments
Benjamin Burton, Arne Hillebrand, Maarten Löffler, Saul Schleimer, Dylan Thurston, Stephan Tillmann, Wouter van Toll
In 34th European Workshop on Computational Geometry (EuroCG), pp. 66:1-6, 2018.


Motivated by motion planning applications, we study 2-dimensional surfaces embedded in 3-dimensional space with the property that their vertical projection is an immersion. We provide bounds on the complexity of a triangulation of such a surface, given that the projection of the boundary is a polygon with m segments. We then show how these bounds lead to efficient algorithm to compute such a triangulation. Finally, we relate our result to concrete motion planning setting and review related open questions.

BibTeX citation

    author = {Burton, B. and Hillebrand, A. and L\"offler, M. and Schleimer, S. and Thurston, D. and Tillmann, S. and {van Toll}, W.},
    title = {On the Topology of Walkable Environments},
    booktitle = {Proceedings of the 34th European Workshop on Computational Geometry (EuroCG)},
    year = {2018},
    pages = {66:1-6}