SafeRect and Safesphere Safe Sphere Q Query Obiect Q7 Q3 Q5 SafeRect
16 SafeRect and SafeSphere
Computing the safe regions If object o is contained in a query, choose one such query rectangle and determine the relevant intersecting or contained query rectangles If object o is not contained in a query rectangle, we consider all query rectangles as relevant. Let e be the set of relevant query rectangles Take object o as the origin and determine which relevant rectangles lie in which of the four induced quadrants. For each quadrant, sort the corner vertices of query rectangles that fall into this quadrant. For each quadrant determine the dominating points The dominating points create a staircase for each quadrant. Use the staircases to find the empty rectangle with the maximum area (using the property that a largest empty rectangle touches at least one corner of the four staircases) 17
17 Computing the Safe Regions ◼ If object O is contained in a query, choose one such query rectangle and determine the relevant intersecting or contained query rectangles. If object O is not contained in a query rectangle, we consider all query rectangles as relevant. Let E be the set of relevant query rectangles. ◼ Take object O as the origin and determine which relevant rectangles lie in which of the four induced quadrants. For each quadrant, sort the corner vertices of query rectangles that fall into this quadrant. For each quadrant determine the dominating points. ◼ The dominating points create a staircase for each quadrant. Use the staircases to find the empty rectangle with the maximum area (using the property that a largest empty rectangle touches at least one corner of the four staircases)