The 2-Center Problem with Obstacles

✍ Scribed by Dan Halperin; Micha Sharir; Ken Goldberg

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 190 KB
• Volume: 42
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1194

✦ Synopsis

Given a set S of n points in the plane and a set O of pairwise disjoint simple polygons with a total of m edges, we wish to find two congruent disks of smallest radius whose union covers S and whose centers lie outside the polygons in O (referred to as locational constraints in facility location theory). We present an algorithm to solve this problem in randomized expected time O m log 2 mn + mn log 2 n log mn . We also present an efficient approximation scheme that constructs, for a given ε > 0, two disks as above of radius at most 1 + ε r * , where r * is the optimal radius, in time O 1/ε log 1/ε m log 2 m + n log 2 n or in randomized expected time O 1/ε log 1/ε m + n log n log mn .