MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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