Intersection points of straight line segment with Voronoi diagram

Question

Hi,

I need to find the x,y points of intersection of a vertical line with the edges of the Voronoi cells it goes through in a defined, rectangular plane region with a given Voronoi tesselation. Is there any computationally efficient method to do this?

Thanks

Answer 1

The paper by Chazelle and Liu,

"Lower bounds for intersection searching and fractional cascading in higher dimension." 2001. (ACM link)

shows that for planar convex subdivisions, the answer is Yes, there is a computationally efficient method if you allow quadratic storage, but No if you insist on subquadratic storage:

---

  

---

Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

Answer 2

The question seem to be nearly as hard as finding Voronoi diagram.

In other words, you have a collection of functions of the form $$f_i(t)=t^2+a_i{\cdot}t+b_i$$ and you need to find the maximal interval $[c_i,d_i]$ where $$f_i=\min_{j}\{f_j\}.$$

Yo will get the same answer, if instead of $f_i$, you use the functions $$h_i(t)=a_i{\cdot}t+b_i=f_i(t)-t^2$$ which are linear. I.e., your problem is equivalent to the classical problem in linear programming --- choose you favorite method.