Minimum spanning circle

Posted on 2005-04-25
Medium Priority
Last Modified: 2008-03-04
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
Question by:Anuhya
LVL 45

Expert Comment

ID: 13857118
Hi Anuhya,



Author Comment

ID: 13857190
hey but i wanted a proof  not the articel found online, that i could search too please reply fast
LVL 45

Accepted Solution

sunnycoder earned 672 total points
ID: 13857279
http://theory.stanford.edu/~megiddo/pdf/circspr.pdf  -- discussion section refers to how the proof presented is infact related to voronoi diagrams

    Computational Geometry in C (2nd Ed.)
    Joseph O'Rourke, Cambridge University Press 1998,
Page 195 has some details
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.


Author Comment

ID: 13857305
thanx i found that already but didnt know how to put that stuff as proof to compute smallest circle , well....anything more specific please let me know and i didnt understand the relavance of page 195...is  sit the theorem 6.2.1????
LVL 22

Assisted Solution

NovaDenizen earned 664 total points
ID: 13862747
There are going to be at least two points from the set on the edge of the bounding circle.  This means that all of these edge points will be the same distance away from the circle's centerpoint, and they will all be the furthest points away from the center point.  So the centerpoint must lie on the line segment (or vertex, when there are more than 2 edge points) where all of the edge points' regions join.

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.
LVL 85

Assisted Solution

ozo earned 664 total points
ID: 13863169

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

807 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question