Optimal Point Movement for Covering Circular Regions

Optimal Point Movement for Covering Optimal Point Movement for Covering Circular Regions Circular Regions Haitao Wang Utah State University ISAAC 2012 Joint work with Danny Z. Chen, XuehouTan, and GangshanWu

Motivation Motivation Mobile sensor barrier coverage A mobile sensor r a sensor

Motivation Motivation Protect a region by sensors Full coverage of region

Motivation Motivation Barrier coverage: only covering its border The border is the barrier intruder

Mobile sensors Mobile sensors How to move sensors to minimize the movement?

Our problem: a simplified version Our problem: a simplified version The region is a circle C Sensors are given inside C Move all sensors to C to form a regular n-gon The sensor range is explicitly determined Objective: min-max: minimize the maximum sensor movement

Previous work O(n3.5log n) time, Bhattacharya et al. 2009 O(n2.5log n) time, Tan and Wu, 2010 Our result O(nlog3n) time Dynamically maintain the maximum matching of a circular convex bipartite graph Support vertex insertions/deletions O(log2n) time each

The difficulty The difficulty

The difficulty The difficulty The optimal solution (OPT) happens at some moment during the rotation

The decision version The decision version Given a distance d, determine whether it is possible to move the sensors to form a regular n-gon on C such that the maximum sensor movement is d If yes, d is a feasible distance, and the n-gon is a feasible solution d

An overview of our approach An overview of our approach d*: the maximum sensor movement in OPT The key idea: Find a set S of distances, such that d* S d*must be the smallest feasible distance in S A straightforward solution: Sort all distances in S Find d*in S by binary search need an algorithm for the decision version Two challenges: How to find S (as small as possible)? Design an efficient algorithm for the decision version

Dealing with the first challenge Dealing with the first challenge For each red point pi, xi : is the point on C closest to pi pi : the position of pion C in an OPT center of C pi pi pi xi

Observation (previous work) Observation (previous work) Suppose |pip i|=d*in an OPT, then p iis xi, or there is another sensor pjsuch that |pip i|=|pjp j|, and if we rotate all blue points in either direction, one of |pip i|and |pjp j| increases and the other one decreases pj pi p j xi= p i pi pjincreases pidecreases pi

Observation (previous work) Observation (previous work) Suppose in an OPT, pimoves the largest distance, then p iis xi, or S1: the set of all such distances |pip i| there is another sensor pjsuch that |pip i= pjp j|, and if we rotate the solution in either direction, one of |pip i|and |pjp j| increases and the other one decreases S2: the set of all such distances |pip i|=|pjp j| Let S = S1 S2, and then d* S What is the size of S? |S1|= n |S2|= O(n3) (previous work)

Our approach Our approach First challenge: Find a smaller set S2with |S2|=O(n2) S2 can be implicitly determined and sorted Correspond to the intersections of n pseudo-lines the y-coordinates of the intersections Only need to implicitly search the pseudo-line arrangement Second challenge: a new algorithm for the decision version Previous work: O(n3.5) Our result: O(nlog2n)

The decision algorithm The decision algorithm Given a distance d, whether d is a feasible distance? If d is feasible, a feasible solution happens at some moment during the rotation

Two difficulties Two difficulties How to discretize the rotation? For each candidate position, how to determine whether there is a feasible solution?

Tackle the second difficulty Tackle the second difficulty For each candidate position, whether it is possible to move all red points to blue points within maximum moving distance d? Observation: qimust be on the brown circular segment d qi pi

Tackle the second difficulty Tackle the second difficulty Build a bipartite graph G connect each red point to all blue points on its circular segment on C Observation: It is feasible solution if and only if there is a perfect matching in G qi pi

Tackle the first difficulty Tackle the first difficulty How to discretize the rotation? key: determine when the graph G changes Totally 2n vertex insertions and deletions Need to dynamically maintain the maximum matching pi

G is a circular convex bipartite graph G is a circular convex bipartite graph We build a data structure in O(nlog2n) time to dynamically maintain the maximum matching in G O(log2n) time for each vertex insertion/deletion The decision problem is solved in O(nlog2n) time pj pi

Conclusion Conclusion An O(nlog3n) time new algorithm Is further improvement possible? Improve the O(nlog2n) time decision algorithm Improve the O(log2n) time maximum matching update

Thank you Thank you Questions?