Loading...
Please wait, while we are loading the content...
Similar Documents
The 2-Center Problem with Obstacles (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Halperin, Dan Sharir, Micha Goldberg, Ken |
| Abstract | 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 nd 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 ecient 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))). 1 |
| File Format | |
| Volume Number | 32 |
| Journal | Journal of Algorithms |
| Language | English |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | 2-center Problem Expected Time Congruent Disk Locational Constraint Optimal Radius Pairwise Disjoint Simple Polygon Ecient Approximation Scheme Facility Location Theory |
| Content Type | Text |
| Resource Type | Article |
