A Note on Minimum-Cost Coverage by Aligned Disks

Details A Note on Minimum-Cost Coverage by Aligned Disks A Note on Minimum-Cost Coverage by Aligned Disks

2012-02-22

arxiv.org/abs/1202.4821v2

Computer Science

Computational Geometry

6 pages, 1 figure

Scientific paper

In this paper, we consider a facility location problem to find a minimum-cost coverage of n point sensors by disks centered at a fixed line. The cost of a disk with radius r has a form of a non-decreasing function f(r) = r^a for any a >= 1. The goal is to find a set of disks under Lp metric such that the disks are centered on the x-axis, their union covers the n points, and the sum of the cost of the disks is minimized. Alt et al. [1] presented an algorithm in O(n^4 log n) time for any a > 1 under any Lp metric. We present a faster algorithm for this problem in O(n^2 log n) time for any a > 1 and any Lp metric.

Affiliated with

Also associated with

No associations

Rating

A Note on Minimum-Cost Coverage by Aligned Disks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on Minimum-Cost Coverage by Aligned Disks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on Minimum-Cost Coverage by Aligned Disks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-414665