Solved

# Minimum spanning circle

Posted on 2005-04-25
Medium Priority
316 Views
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
0
Question by:Anuhya

LVL 45

Expert Comment

ID: 13857118
Hi Anuhya,

http://www.cs.mcgill.ca/~netty/html/507.html

Cheers!
sunnycoder
0

Author Comment

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

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
www-ma2.upc.es/~vera/mesa.ps

Computational Geometry in C (2nd Ed.)
Joseph O'Rourke, Cambridge University Press 1998,
Page 195 has some details
0

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????
regards
Anuhya
0

LVL 22

Assisted Solution

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.
0

LVL 85

Assisted Solution

ozo earned 664 total points
ID: 13863169
0

## Featured Post

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 …
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
Course of the Month13 days, 20 hours left to enroll