patternMinor
Number of double wedges containing a point
Viewed 0 times
containingnumberpointdoublewedges
Problem
We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now these $n$ double wedges can intersect each other.
Our query is as follows: given a point, we want to find how many double wedges it's contained in. We want to be able to make this query in $O(\log n)$ time, using a data structure that can be constructed (preprocessed) in $O(n^2\log n)$ time and $O(n^2)$ space.
This exercise is from the de Berg's computational geometry book in the chapter about arrangement of lines, so I was thinking we can do some kind of incremental construction by adding the double wedges one by one, but I can't seem to think of the data structure.
Our query is as follows: given a point, we want to find how many double wedges it's contained in. We want to be able to make this query in $O(\log n)$ time, using a data structure that can be constructed (preprocessed) in $O(n^2\log n)$ time and $O(n^2)$ space.
This exercise is from the de Berg's computational geometry book in the chapter about arrangement of lines, so I was thinking we can do some kind of incremental construction by adding the double wedges one by one, but I can't seem to think of the data structure.
Solution
The set of $2n$ lines on the plane form a well studied Arrangement of lines, which is a type of planar subdivision, composed of vertices, edges and faces. This planar subdivision used to be represented by DCEL. There are two types of algorithms, which can convert a bare set of lines into the DCEL - plane sweeping algorithm with time complexity $O(n^2log(n))$, and incremental one with time complexity $O(n^2)$. Both these types are described in this book (Item 8.3). The resulting subdivision will have $O(n^2)$ faces.
Given a planar subdivision with $O(n^2)$ faces we can convert it further into a hierarchical data structure, which can be used to locate a face, containing any query point, in $O(log(n))$ time. This is a topic with long history - please see the Point location page for more information.
So, if we assign a number of double wedges, containing a point, to each face of the planar subdivision - we'll solve the exercise. Let's find out how we can do just that.
Each double wedge defines four parts of the plane, and we need to define clearly, what parts are inside the wedge. In order to do that we'll split each boundary line into two rays - one pair of "incoming" rays and one pair of "outcoming" rays. We'll consider a part of the plane, lying to the left of each such ray, to be inside the double wedge.
The direction of these rays can be used to calculate the number of intersecting double wedges (called below an intersection number), corresponding to each face of the planar subdivision. It's easy to see, that these numbers for adjacent faces differ by one. Even more, if we jump from some face to another face over a boundary edge, directed from the left to the right, we'll need to increment this number. If the boundary edge is directed from the right to the left, then this number needs to be decremented. An example of two double wedges $w1$ and $w2$ with assigned intersection numbers (in red) is below.
So, the algorithm to assign intersection numbers to faces comprises of two steps:
Step 1. Take an arbitrary initial face and calculate its intersection number, using all the $n$ double wedges - it can be done in $O(n)$ time.
Step 2. Traverse all the faces of the planar subdivision, starting from the initial face and assigning the intersection number using boundary edges direction as described above - it can be done by the DFS in $O(n^2)$ time.
Given a planar subdivision with $O(n^2)$ faces we can convert it further into a hierarchical data structure, which can be used to locate a face, containing any query point, in $O(log(n))$ time. This is a topic with long history - please see the Point location page for more information.
So, if we assign a number of double wedges, containing a point, to each face of the planar subdivision - we'll solve the exercise. Let's find out how we can do just that.
Each double wedge defines four parts of the plane, and we need to define clearly, what parts are inside the wedge. In order to do that we'll split each boundary line into two rays - one pair of "incoming" rays and one pair of "outcoming" rays. We'll consider a part of the plane, lying to the left of each such ray, to be inside the double wedge.
The direction of these rays can be used to calculate the number of intersecting double wedges (called below an intersection number), corresponding to each face of the planar subdivision. It's easy to see, that these numbers for adjacent faces differ by one. Even more, if we jump from some face to another face over a boundary edge, directed from the left to the right, we'll need to increment this number. If the boundary edge is directed from the right to the left, then this number needs to be decremented. An example of two double wedges $w1$ and $w2$ with assigned intersection numbers (in red) is below.
So, the algorithm to assign intersection numbers to faces comprises of two steps:
Step 1. Take an arbitrary initial face and calculate its intersection number, using all the $n$ double wedges - it can be done in $O(n)$ time.
Step 2. Traverse all the faces of the planar subdivision, starting from the initial face and assigning the intersection number using boundary edges direction as described above - it can be done by the DFS in $O(n^2)$ time.
Context
StackExchange Computer Science Q#123349, answer score: 3
Revisions (0)
No revisions yet.