D*******r
发帖数: 37 | 1 how to compute the farthest-point voronoi diagram in O(nlogn)?
Is there any way similar to the forturne algorithm for the nearst-point
voronoi diagram?
Thanks! | y***u
发帖数: 101 | 2 Yes you can. Can be reduced to 3D convex hull.
【在 D*******r 的大作中提到】
: how to compute the farthest-point voronoi diagram in O(nlogn)?
: Is there any way similar to the forturne algorithm for the nearst-point
: voronoi diagram?
: Thanks!
| l*****g
发帖数: 49 | 3
yes, the farthest-point voronoi diagram can be computed in time
O(n log n), by any optimal algorithm for 3D convex hull (not
a plane-sweep algorithm similar to fortune's)
take any classical textbook in computational geometry and you will
find the following information (for example, Shamos and Preparata's):
the farthest-point voronoi diagram (in the plane) is the projection
of the lower envelop of n (special) planes in 3D. The lower envelop is in fact
the dual of a convex hull, so any optimal co
【在 D*******r 的大作中提到】
: how to compute the farthest-point voronoi diagram in O(nlogn)?
: Is there any way similar to the forturne algorithm for the nearst-point
: voronoi diagram?
: Thanks!
|
|
