14
$\begingroup$

I try to solve the following coverage problem.

There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers are covered by any transmitter. All reveivers and transmiters are represented by their $x$ and $y$ coordinates.

The most advanced solution I can come with takes $O(n^2\log n)$. For every receiver sort all transmitter by it distance to this current receiver, then take the transmitter with shortest distance and this shortest distance should be within 0.5 km.

But the naive approach looks like much better in time complexity $O(n^2)$. Just compute all distance between all pairs of transmitter and receiver.

I am not sure if I can apply range-search algorithms in this problem. For example kd-trees allow us to find such ranges, however I never saw an example, and I am not sure if there are kind of range-search for circles.

The given complexity $O(n\log n)$ assumes that the solution should be somehow similar to sorting.

$\endgroup$
  • 1
    $\begingroup$ If expected time $O(n \log n)$ is okay, I think you could build an $kd$-tree over the transmitters (taking time $O(n \log n)$), and then perform a nearest neighbor query for each receiver (taking an average of $O(\log n)$ time for each receiver). This should to the trick, but I assume you need worst case complexity. There seems to be some tricks for speedup when you are performing multiple nearest neighbor queries in a $kd$-tree. $\endgroup$ – utdiscant May 25 '12 at 6:54
  • 1
    $\begingroup$ I guess a sweep line algorithm can do the trick: sort both transmitters and receivers by x-coordinate and step through the list. Clever management of the set of viable transmitters is essential. $\endgroup$ – Raphael May 25 '12 at 9:41
  • $\begingroup$ @Raphael, can you please elaborate a little more, it looks like it's gonna be very slow in worst case. $\endgroup$ – com May 26 '12 at 7:06
  • 1
    $\begingroup$ I think it is worth taking a look at Fortune's algorithm for computing a Voronoi diagram in the plane. It works in $O(n\log n)$, and given a Voronoi diagram, your problem becomes easy. $\endgroup$ – Syzygy May 26 '12 at 13:40
4
$\begingroup$

You can use the Voronoi diagram, together with Kirkpatrick's data structure to solve this problem.

Like Raphael and Syzygy suggested, you can use Fortune's (sweepline) algorithm to create the Voronoi diagram. Worst case time: $\mathcal{O}(n \log n)$.

The Voronoi diagram will have a bunch of polygons, each one containing a transmitter. Any point within the polygon is closest to that transmitter. Thus, if you can find out which polygon contains the receiver, you can find the closest transmitter to it by somehow finding out which polygon it is in. After that, you check if that transmitter is within $1\ \text{km}$.

To determine which Voronoi polygon contains the receiver, you first triangulate each polygon in the diagram. Now you have a triangle mesh. Next you use Kirkpatrick's data structure to locate any triangle containing a given point in $\mathcal{O}(\log n)$ time, worst case. Constructing Kirkpatrick's data structure takes $\mathcal{O}(n\log n)$ worst case. Once you know the triangle, you will know the polygon that contains it, and thus the closest transmitter. Doing this for all the receivers will be $\mathcal{O}(n\log n)$, worst case.

Each cell in a Voronoi diagram is a convex polygon, possibly unbounded.

...

The number of vertices [of a Voronoi diagram of n sites] V ≤ 2n-5

www.cs.arizona.edu

Each polygon in a Voronoi diagram is a convex polygon. Therefore, since triangulation of a convex polygon takes $\Theta(v)$ time, $v$ being the number of of sides, we can triangulate each cell efficiently. If you fear that triangulation can be pathological (that we might have $n$ cells, each with $n$ sides), then consider this. The Voronoi diagram has $\mathcal{O}(n)$ vertices (see quote above). The triangulation of the Voronoi diagram is planar, and so is a sparse graph, and thus has $\mathcal{O}(n)$ edges and faces. Thus triangulation of a particular cell might take $\mathcal{O}(n)$, but the overall triangulation also takes $\mathcal{O}(n)$. (Basically, we will not encounter many cells with $\mathcal{O}(n)$ sides, this would result too many triangles for a planar graph).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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