Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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:


   Chazelle
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|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|improve this answer

Your Answer

 
discard

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.