Walking around fat obstacles

✍ Scribed by L.Paul Chew; Haggai David; Matthew J. Katz; Klara Kedem

• Book ID: 104136731
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 189 KB
• Volume: 83
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00321-0

✦ Synopsis

We prove that if an object O is convex and fat then, for any two points a and b on its boundary, there exists a path on O's boundary, from a to b, whose length is bounded by the length of the line segment ab times some constant β. This constant is a function of the dimension d and the fatness parameter. We prove bounds for β, and show how to efficiently find paths on the boundary of O whose lengths are within these bounds. As an application of this result, we briefly consider the problem of efficiently computing short paths in R d in the presence of disjoint convex fat obstacles.