4
$\begingroup$

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.

enter image description here

$\endgroup$
3
  • $\begingroup$ Does a sweep line algorithm work? See e.g., en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm, en.wikipedia.org/wiki/Persistent_data_structure $\endgroup$
    – D.W.
    Mar 30, 2020 at 17:12
  • $\begingroup$ @D.W. I don't think so, because we can't afford to do a sweep for every query. I think the solution has something to do with reducing it to some type of point location problem, but I'm not sure how to proceed with this. $\endgroup$
    – sedrick
    Mar 30, 2020 at 17:20
  • $\begingroup$ That's not what I meant -- one combines a sweepline algorithm with a persistent data structure to achieve query time closer to $O(\log n)$ per query, not a full sweep per query. $\endgroup$
    – D.W.
    Mar 30, 2020 at 21:35

1 Answer 1

4
$\begingroup$

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.

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.

Two double wedges

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.

$\endgroup$
4
  • $\begingroup$ Note that the book you are referring to is the same book that contains the exercise in the question. $\endgroup$
    – Discrete lizard
    May 24, 2020 at 9:02
  • $\begingroup$ @DiscreteLizard - it's just a reminder for the OP to read this book more thoroughly... BTW, there are no such exercise in this book (3d Ed) $\endgroup$
    – HEKTO
    May 24, 2020 at 15:40
  • 1
    $\begingroup$ Well, this exercise is not in there literally, but this is what remains of exercise 8.15 after reformulating the problem as suggested in 8.15 a. $\endgroup$
    – Discrete lizard
    May 24, 2020 at 21:17
  • $\begingroup$ @DiscreteLizard - good find, thanks! $\endgroup$
    – HEKTO
    May 24, 2020 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.