Solved

Posted on 2005-04-25

Show how the furthest-point Vorronoi diagram can be used to compute the smallest-circle that surrounds a given point set.Assume F(P) is available

courtesy Joseph O Rourke 5.5.6

courtesy Joseph O Rourke 5.5.6

6 Comments

regards

anuhya

www-ma2.upc.es/~vera/mesa.

Computational Geometry in C (2nd Ed.)

Joseph O'Rourke, Cambridge University Press 1998,

Page 195 has some details

regards

Anuhya

So, to find the smallest bounding circle it looks like you just have to examine all the line segments in the furthest point voronoi, and find the minimum furthest distance on them. You only need to check up to 3 points for each segment: the 2 endpoints, and the point on the segment closest to either furthest point for that segment. The closest point is easy to find, since it is the intersection of the segment and a line drawn between the two furthest points for that segment.

A slight refinement would be to check each vertex once, then check the closest point for each segment.

There might be a better way to seek out the minimum segment, like a greedy algorithm that automatically seeks its way along the voronoi edge graph to the minimum. I can't think of a method or a proof for it right away.

Here is a java example

http://www.cs.brown.edu/people/tor/java/mec/

http://www.cs.brown.edu/pe

Title | # Comments | Views | Activity |
---|---|---|---|

Need help with programming in R stats software | 6 | 23 | |

File Server Growth. | 9 | 45 | |

invest money into checking/savings account | 4 | 87 | |

wordsWithoutList challenge | 24 | 62 |

This video discusses moving either the default database or any database to a new volume.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**20** Experts available now in Live!