Minimum spanning circle

Posted on 2005-04-25
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

    Hi Anuhya,


    Author Comment

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

    Accepted Solution

    by:  -- 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

    Author Comment

    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  sit the theorem 6.2.1????
    LVL 22

    Assisted Solution

    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 84

    Assisted Solution


    Featured Post

    Top 6 Sources for Identifying Threat Actor TTPs

    Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

    Join & Write a Comment

    Suggested Solutions

    Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! How to Know You are Making a Difference at EE In August, 2013, one …
    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 video discusses moving either the default database or any database to a new volume.
    Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

    754 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

    Need Help in Real-Time?

    Connect with top rated Experts

    20 Experts available now in Live!

    Get 1:1 Help Now