| y (2007) | |||||||||||||||
Abstract | |||||||||||||||
| This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q with k and n vertices, respectively (k! n), the number of edges and vertices bounding a single face of the complement of the Minkowski sum P \Phi Q is \Theta(nkff(k)) in the worst case. The lower bound comes from a construction based on lower envelopes of line segments; the upper bound comes from a combinatorial bound on Davenport-Schinzel sequences that satisfy | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||