Approximating a Motorcycle Graph by a Straight Skeleton
Stefan G. Huber, Martin Held · 2011
We investigate how a straight skeleton can be used to approximate a motorcycle graph. We explain how to construct a planar straight-line graph G such that the straight skeleton of G reveals the motorcycle graph of M, for every given finite set M of motorcycles. An application of our construction is a proof of the P-completeness of the construction problem of straight skeletons of planar straight-line graphs and simple polygons with holes.