Optimal Point Movement for Covering Circular Regions

Details Optimal Point Movement for Covering Circular Regions Optimal Point Movement for Covering Circular Regions

2011-07-06

arxiv.org/abs/1107.1012v1

Computer Science

Computational Geometry

18 pages, 2 figures

Scientific paper

Given $n$ points in a circular region $C$ in the plane, we study the problems of moving the $n$ points to its boundary to form a regular $n$-gon such that the maximum (min-max) or the sum (min-sum) of the Euclidean distances traveled by the points is minimized. The problems have applications, e.g., in mobile sensor barrier coverage of wireless sensor networks. The min-max problem further has two versions: the decision version and optimization version. For the min-max problem, we present an $O(n\log^2 n)$ time algorithm for the decision version and an $O(n\log^3 n)$ time algorithm for the optimization version. The previously best algorithms for the two problem versions take $O(n^{3.5})$ time and $O(n^{3.5}\log n)$ time, respectively. For the min-sum problem, we show that a special case with all points initially lying on the boundary of the circular region can be solved in $O(n^2)$ time, improving a previous $O(n^4)$ time solution. For the general min-sum problem, we present a 3-approximation $O(n^2)$ time algorithm, improving the previous $(1+\pi)$-approximation $O(n^2)$ time algorithm. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm can handle each vertex insertion or deletion on the graph in $O(\log^2 n)$ time. This result is interesting in its own right.

Affiliated with

Also associated with

No associations

Rating

Optimal Point Movement for Covering Circular Regions 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 Optimal Point Movement for Covering Circular Regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Point Movement for Covering Circular Regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-677464