Connecting points in the presence of obstacles in the plane.
Michael M. Hoffmann, Csaba D. Tóth · 2002
Given a point set P and a set B of polygonal obstacles in the plane, we consider planar geometric graphs connecting the points of P and crossing few obstacles from B. We describe two finite constructions and an algorithm. The constructions show that it is not possible to draw a spanning tree or Hamiltonian circuit without crossing an obstacle a certain number of times. The algorithm shows that the vertices of axis-parallel rectangles -- in contrast to general rectangles -- can be connected by a Hamiltonian circuit without crossing obstacles.