Efficient Algorithms for Finding the Smallest Enclosing Disc
Smallest enclosing disc
Chapter 4 of the text
Slides prepared by van Krevald
Facility location
•
Given a set of objects, locate a central place
such that the farthest object to the central
place is as close as possible.
Geometry
The smallest circle must pass through
some points
•
At least one point
The smallest circle must pass through
some points
•
At least two points
The smallest circle must pass through
some points
Randomized algorithm
•
In case of LP we used the fact that when the current
optimal vertex is contained in the next half-space, it
doesn’t change, otherwise the optimal vertex lies on
the boundary of the half plane.
A similar statement
can be made for the smallest enclosing disc problem.
•
P={p1
,p
2
, …,p
n
}; P
i
={p1
,p
2
, …, p
n
}
•
D
i
: the smallest enclosing disc of P
i.
Algorithm
MiniDisc(P)
Algorithm
MiniDisc(P)
The critical step occurs when p
i
does not belong to D
i-1.
Algorithm
MiniDiscWithPoint(P)
Algorithm
MiniDiscWithPoint(P)
How do you compute the minimum enclosing disc
constrained to pass through two points?
Algorithm
MiniDiscWith2Points(P)
This finally completes the algorithm for planar point sets.
Analysis of MiniDisc(P)
•
MiniDiscWith2Points runs in linear time.
•
The running time of MiniDiscWithPoint is O(n) as long as
we don’t count the time spent in calls to
MiniDiscWith2Points.
•
What is the probability of having to make such a call?
•
Backward analysis
–
Suppose we have computed D
i
of P
i
and having q on the
boundary.
–
Imagine we remove one of the points of P
i
. With probability 2/i,
the enclosing circle will shrink.
–
The expected running time MiniDiscWithPoint is
Analysis of MiniDisc(P)
•
Applying the same argument once more, we find that the
expected running time of MiniDisc is O(n) as well.
•
The algorithm easily generalizes to higher d dimension.
•
In this case we need a routine of the following type
MiniDiscWith-m-Points(P
i
,q
1
, q
2
, …, q
m
)
•
The running time is expected O(n).
Explore algorithms for finding the smallest enclosing disc for a given set of objects, optimizing central placement, and ensuring minimal distance from objects. The process involves identifying critical steps, computations for passing through points, and analysis highlighting linear running times. Discover the intricacies of randomized algorithms and optimizations in geometry problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Smallest enclosing disc Chapter 4 of the text Slides prepared by van Krevald
Facility location Given a set of objects, locate a central place such that the farthest object to the central place is as close as possible.
The smallest circle must pass through some points At least one point
The smallest circle must pass through some points At least two points
The smallest circle must pass through some points
Randomized algorithm In case of LP we used the fact that when the current optimal vertex is contained in the next half-space, it doesn t change, otherwise the optimal vertex lies on the boundary of the half plane. A similar statement can be made for the smallest enclosing disc problem. P={p1,p2, ,pn}; Pi={p1,p2, , pn} Di: the smallest enclosing disc of Pi.
Algorithm MiniDisc(P) The critical step occurs when pi does not belong to Di-1.
Algorithm MiniDiscWithPoint(P) How do you compute the minimum enclosing disc constrained to pass through two points?
Algorithm MiniDiscWith2Points(P) This finally completes the algorithm for planar point sets.
Analysis of MiniDisc(P) MiniDiscWith2Points runs in linear time. The running time of MiniDiscWithPoint is O(n) as long as we don t count the time spent in calls to MiniDiscWith2Points. What is the probability of having to make such a call? Backward analysis Suppose we have computed Di of Pi and having q on the boundary. Imagine we remove one of the points of Pi. With probability 2/i, the enclosing circle will shrink. The expected running time MiniDiscWithPoint is
Analysis of MiniDisc(P) Applying the same argument once more, we find that the expected running time of MiniDisc is O(n) as well. The algorithm easily generalizes to higher d dimension. In this case we need a routine of the following type MiniDiscWith-m-Points(Pi,q1, q2, , qm) The running time is expected O(n).
