Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network

Details Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network

2010-06-15

arxiv.org/abs/1006.2955v1

Computer Science

Computational Geometry

16 pages, 5 figures,

Scientific paper

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments in sensor networks. A line segment ` is said to be covered if it intersects the sensing regions of at least one sensor distributed in that region. We show that the problem of ?nding the minimum number of sensors needed to cover each member in a given set of line segments in a rectangular area is NP-hard. Next, we propose a constant factor approximation algorithm for the problem of covering a set of axis-parallel line segments. We also show that a PTAS exists for this problem.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network 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 Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithm for Line Segment Coverage for Wireless Sensor Network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104948