1
$\begingroup$

Given a set of Voronoi edges. Each edge consists of (indices of, pointers to) 4 points: $\mathrm{left}$ and $\mathrm{right}$ are sites, $\mathrm{begin}$ and $\mathrm{end}$ are vertices (one of them or even both (in case if all the sites lies on a straight line) may point to infinity). $\angle \Big(\overrightarrow{(\mathrm{left},\mathrm{right})},\overrightarrow{(\mathrm{begin},\mathrm{end})}\Big) \equiv +{\pi \over 2}$. Sites and vertices lies in two dedicated arrays. Sites are lexicographically ordered (i.e. by $x$ then also by $y$), vertices also can be easily sorted in the same manner.

What is the best way to locate point in Voronoi diagram defined as above (here, find closest site)? What are the best online and best offline ways (if differs)? I sure both of them can be constructed in linear-logarithmic time, but maybe one of them can have much lesser constant factor?

Improve this question
$\endgroup$
1
  • $\begingroup$ You may wish to specify in what sense of 'online' you're interested in. Adding more query points? More Voronoi points? More Voronoi edges? $\endgroup$
    – Discrete lizard ♦
    Jan 26, 2018 at 15:09

1 Answer 1

Reset to default
1
$\begingroup$

I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points. Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of convex cells, we instead can construct a triangulation of the Voronoi diagram in $O(n)$ that can answer point location queries in $O(\log n)$, which is in fact optimal$^*$. (The complexity for the triangulation is in terms of the edges, but this doesn't matter as the number of edges of a Voronoi diagram is it most $3n-6$).

So, if we are given a Voronoi diagram on $n$ sites and $m$ query points at once, this gives an $O(n+m\log n)$ time algorithm. It makes no difference when we get the query points, so this algorithm is also online in that sense.

It isn't very clear what would be provided if the sites would be 'online', as some edges will be removed and others added when adding sites. If the number of edges added and removed are given, there is a constant number of them and the triangulation can be updated in constant time, so the total running time would remain $O(n+m\log n)$.

Another approach that may not be as good in theory but might work better in practice is to use quadtrees: you can store the set of closest sites for every square in the tree and partition the squares until the size of all those sets is small enough. Then simply locate the square containing the query point and compare all sites in the set for that square to find the nearest site.

*: See the paper: Kirkpatrick, David. "Optimal search in planar subdivisions." SIAM Journal on Computing 12.1 (1983): 28-35.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I am sure convexity of the polygons can be used to improve more general algorithms. $\endgroup$
    – Tomilov Anatoliy
    Jan 26, 2018 at 16:51
  • $\begingroup$ Quad tree has quadratic worst time complexity. Let's imagine concentric sites and small cloud of query points near the center. One of the sites is slightly shifted to the center. $\endgroup$
    – Tomilov Anatoliy
    Jan 26, 2018 at 17:00
  • $\begingroup$ I mean offline in other sense: given Voronoi diagram of M sites and given N points to locate. All at once. I can imagine better algorithm: walk trough lexicographically ordered array of both query points and Voronoi diagram vertices and keep hash table of current edges (i.e. ones crossed x = const line, where x is ordinate of current vertex/query point). When vertex encountered remove ends and add begins (edges). When query point is encountered, dump all edges from that hash table into vertically ordered tree (here convexity used) and test that point. When remove - remove from both. $\endgroup$
    – Tomilov Anatoliy
    Jan 26, 2018 at 17:04
  • $\begingroup$ @Orient Ah yes, when we have convex subdivisions, we can construct the decomposition in $O(n)$ time, which is optimal. So I think the 'online' case is covered here. For the offline case, the algorithm I suggest runs in $O(M+N\log M)$ time, which I think is hard to improve on. I don't think your suggested method would be efficient (if I understand it correctly): you might encounter $O(N)$ points nearest to a total of $O(M)$ before encountering the first Voronoi vertex, which means testing against every edge gives a $O(NM)$ algorithm. $\endgroup$
    – Discrete lizard ♦
    Jan 26, 2018 at 17:20
  • $\begingroup$ @Orient Yes, quad-trees are bad in theory. But in practice, they often turn out to work. It wasn't clear to me whether you're mostly interested in practical or theoretical answers, so I looked at both perspectives. $\endgroup$
    – Discrete lizard ♦
    Jan 26, 2018 at 17:21

Your Answer

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

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