Grade 7 Science - Diversity of Living Organisms Investigation
Investigate the diversity of living organisms through categorization models, historical classifications, and current scientific methods. Engage in vocabulary practice, current events analysis, and group activities to enhance learning. Assessments include quizzes, worksheets, and tests to evaluate student progress. Focus on evidence collection and learning opportunities for continuous improvement.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Multiple Barriers Coverage Problem in the Plane Shimin Li and Haitao Wang Utah State University WADS 2017, St. John s, Canada
Problem Definition Given a set of ? barriers, ?1,?2, ,??, on a line ? There are ? sensors, ?1,?2, ,??, in the plane with sensing range ? We want to cover all the barriers by moving sensors onto ? Sensors must be finally located at L The goal is minimizing the maximum moving distance of sensors ? ?2 ?3 ?1
Another Problem View The ? barriers are represented by segments on ? The sensing range of a sensor is a horizontal segment of length 2? Try to cover the green segments by moving the yellow ones onto ? The goal is minimizing the maximum moving distance of the yellow segments ? ?2 ?3 ?1
The Line Constrained Case Sensors are all initially given on L ? ?2 ?3 ?1
Previous Works and Our Results The Line Constrained Case: O(n2) time for m=1, Czyzowicz et al. 2009 ?(? log?) time for ? = 1, Chen et al. 2013 Our result: ?((? + ?) ???(? + ?)) time for any ? The General Case: The sensors are given in the plane ?(?3 log?) for ? = 1, Li and Shen, 2015 Our result: ?(??log? loglog? + ??????) time for any ?
Outline The Line Constrained Case The algorithm for the decision problem The algorithm for the optimization problem The General Case The algorithm for the decision problem The algorithm for the optimization problem
The Decision Problem For any given ? > ?, determine whether we can find a feasible solution with the maximum moving distance no greater than ?. Our result: ?(? + ?) time A simple greedy Algorithm
Main Idea Stage I: Shift all sensors rightwards by ? ? Stage II: Move the sensors leftwards one by one as little as possible to cover each barrier from left to right ?2 ?1
The Optimization Problem ? : the optimal objective value, i.e., the maximum sensor movement in an optimal solution Goal: Compute ?* A value ? is called a feasible value if ? ?* It is possible to cover all barriers by moving sensors with distances at most
Main Idea The order preserving property There exists an optimal solution in which the sensors have the same order as in the input Find a set S of candidate values that contains ? Find the smallest feasible value of S by using the decision algorithm For example, sort the elements of S, and then binary search
The Difficulty S = (mn2) Cannot afford to explicitly compute S Our strategy: Implicitly organize the values of S in ?(?) sorted arrays The main challenge Our main contribution Find ? from the sorted arrays using a matrix searching technique and our decision algorithm
Three Optimal Solution Configurations ? Case I: B ? Case II: B ? ? Case III:
Candidates Values: Case III i,j si+1, si+2, , sj-1 i,j ?? ?? ?? ?? ??,?=?? ?? ?? ? ? for 1 ? < ? ? ? ??: the ?-coordinate of sensor ?? in the input O(n2) candidate values Can be implicitly organized into O(n) sorted arrays of O(n) elements each, Chen et al. 2013
Candidates Values: Case I i,j,k si+1, si+2, , sj-1 ?? ?? ?? ?? ?? ??,?,?= ?? ??+ ?? ? ? + ? for 1 ? ? ? and 1 ? ? ??: the ?-coordinate of the left endpoint of barrier ?? The total number of such candidate values is (mn2)
Candidates Values: Case II Symmetric to Case I Our main challenge is on how to organize the (mn2) candidate values for these two cases into sorted arrays Our result: In O(m log m) time, we can implicitly form a set of O(n) sorted arrays of O(nm2) elements each such that every candidate value is contained in one of these arrays each array element can be computed in O(log m) time
Observations for 1 ? ? ? and 1 ? ? ??,?,?= ?? ??+ ?? ? ? + ? ??+?,?,?= ??,?,?+ ?? ??,?,?+?= ??,?,? ????+?
Observations (Cont.) ??+?,?,?= ??,?,?+ ?? ??,?,? ??,?,? ??,?,? ??,?,? ?? ??
Observations (Cont.) ??,?,?= ??,?,?+? ????+? ??,?,? ??,?,? ??,?,? ? ???? ??,?,? ?? ???
The Line Constrained Case Time: O((m+n) log(m+n))
The General Case m barriers on L n sensors in the plane, each represented by a horizontal line segment of length 2r and the sensor is the midpoint of each segment ? ?2 ?3 ?1
The Decision Problem For any given ? > ?, determine whether we can find a feasible solution with the maximum moving distance no greater than ?. Our result: ? ? + ?log? A key difference from the line constrained case: The order preserving property does not hold
The decision problem: each sensor is allowed to move at most ??(??,??) ? ? Leftmost point: Rightmost point: ? ? ?? ?? ?? ?? ?? ??+ ? The moving range of ?? on ?
Notation ??(??,??) rightmost coverable point leftmost coverable point ? ? ?? ?? ? ? ? ?+ ? ?? ?? ?? ?? ?? ??+
Our Algorithm: Two Stages Stage I: Shift each sensor ?? to its rightmost ? on ? position ??+ ?? ?? Stage II: Cover the barriers from left to right using the sensors following two criteria Do not move any sensor if possible Otherwise, move the sensors leftwards as little as possible by the order of ??
Stage II Sweep all barriers by a point p on L from let to right Using appropriate sensors to cover the current point p ?2 ?1 Time of the decision algorithm: ? ? + ?log? ? ? + ???????? time if the ri values are already sorted
The Optimization Problem ? : the optimal objective value Goal: Compute ?*
Main Idea The approach for the line-constrained case does not work here The order preserving property does not hold Parameterized the decision algorithm In each step, using the decision algorithm to make the decision Somewhat like parametric search, but no parallel scheme is involved Time: ?(??log? loglog? + ??????)
