Skip to main content
MathOverflow

Return to Answer

Image link broken; now fixed.
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.pngChazelle
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

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 http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

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.
added 44 characters in body
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 NoYes, there is not a computationally efficient method (unlessif you allow quadratic storage), but No if you insist on subquadratic storage:

   Chazelle http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

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 No, there is not a computationally efficient method (unless you allow quadratic storage):

   Chazelle http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

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 http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

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 No, there is not a computationally efficient method (unless you allow quadratic storage):

   Chazelle http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png
Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.