Closest Pair and Convex Hull: Brute Force Approach
Closest Pair and Convex-Hull
By
Brute Force Approach
Dr. Sasmita Kumari Nayak
Computer Science & Engineering
Closest Pair Problem
•
It finds the two closest points in a set of n
points in a given plane.
•
Brute-force algorithm:
Compute the distance between every pair of
distinct points and return the indexes of the
points for which the distance is the smallest.
Cont…
•
Consider the 2D case of the closest pair
problem.
•
The points are specified in a (x, y) coordinates
and the distance between two points p
i
(x
i
, y
i
)
and p
j
(x
j
, y
j
) is the Euclidean distance.
•
Here, it computes the distance between each
pair of distinct points and finds a pair with the
smallest distance
.
Closest Pair
Example
Algorithm of
Closest Pair
Algorithm
BruteForceClosestPoints(
P
)
//
P
is list of points
dmin
← ∞
for
i
← 1
to
n
-1
do
for
j
←
i
+1
to
n
do
d
← sqrt((
x
i
-
x
j
)
2
+ (
y
i
-
y
j
)
2
)
if
d
<
dmin
then
dmin
←
d
;
index
1 ←
i
;
index
2 ←
j
return
index
1,
index
2
Time Complexity of
Closest Pair
Problem
Convex-Hull Problem
•
Polygon is called as a convex polygon if the
angle between any of its two adjacent edges
is always less than 180. Otherwise, it is
called as a concave polygon.
•
Convex hull is the smallest region covering
given set of points.
•
Complex polygons are self-intersecting
polygons.
Cont...
Definition:
the convex hull of a set S of points is the
smallest convex set containing S. ( The smallest
requirement means that the convex hull of S must be a
subset of any convex set containing S.)
Example-1
Example-2
•
Given a set of points in the plane. The convex
hull of the set is the smallest convex polygon
that contains all the points of it.
Example-3
Procedure of Convex-Hull Problem
•
At first, we need to find the points that will serve
as the vertices of the polygon that is called as
“extreme points.”
•
An extreme point of a convex set is a point of this
set that is not a middle point of any line segment
with endpoints in the set.
•
Solving the convex-hull problem in a brute-force
manner is a simple but inefficient algorithm.
•
To find convex polygon such that all points are
either on the boundary or within the polygon.
Time complexity
•
The running time to find the convex polygon
by using the Brute-force approach is O(.n
3
)
Brute-Force Strengths and Weaknesses
•
Strengths
–
wide applicability
–
simplicity
–
yields reasonable algorithms for some important problems
(e.g., matrix multiplication, sorting, searching, string
matching)
•
Weaknesses
–
rarely yields efficient algorithms
–
some brute-force algorithms are unacceptably slow
–
not as constructive as some other design techniques
Exhaustive Search
•
A brute force solution to a problem involving search for an
element with a special property, usually among
combinatorial objects such as permutations, combinations,
or subsets of a set.
•
Ex: Travelling Salesman Problem, Knapsack problem,
Assignment Problem.
Method:
–
generate a list of all potential solutions to the problem in a
systematic manner
–
evaluate potential solutions one by one, disqualifying infeasible
ones and, for an optimization problem, keeping track of the best
one found so far
–
when search ends, announce the solution(s) found
Closest Pair Problem in 2D involves finding the two closest points in a set by computing the distance between every pair of distinct points. The Convex Hull Problem determines the smallest convex polygon covering a set of points. Dr. Sasmita Kumari Nayak explains these concepts using a brute-force algorithm approach.
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
Closest Pair and Convex-Hull By Brute Force Approach Dr. Sasmita Kumari Nayak Computer Science & Engineering
Closest Pair Problem It finds the two closest points in a set of n points in a given plane. Brute-force algorithm: Compute the distance between every pair of distinct points and return the indexes of the points for which the distance is the smallest.
Cont Consider the 2D case of the closest pair problem. The points are specified in a (x, y) coordinates and the distance between two points pi(xi, yi) and pj(xj, yj) is the Euclidean distance. Here, it computes the distance between each pair of distinct points and finds a pair with the smallest distance.
Algorithm of Closest Pair Algorithm BruteForceClosestPoints(P) // P is list of points dmin for i 1 to n-1 do for j i+1 to n do d sqrt((xi-xj)2+ (yi-yj)2) if d < dmin then dmin d; index1 i; index2 j return index1, index2
Time Complexity of Closest Pair Problem
Convex-Hull Problem Polygon is called as a convex polygon if the angle between any of its two adjacent edges is always less than 180. Otherwise, it is called as a concave polygon. Convex hull is the smallest region covering given set of points. Complex polygons are self-intersecting polygons.
Cont... Definition: the convex hull of a set S of points is the smallest convex set containing requirement means that the convex hull of S must be a subset of any convex set containing S.) S. ( The smallest
Example-2 Given a set of points in the plane. The convex hull of the set is the smallest convex polygon that contains all the points of it.
Procedure of Convex-Hull Problem At first, we need to find the points that will serve as the vertices of the polygon that is called as extreme points. An extreme point of a convex set is a point of this set that is not a middle point of any line segment with endpoints in the set. Solving the convex-hull problem in a brute-force manner is a simple but inefficient algorithm. To find convex polygon such that all points are either on the boundary or within the polygon.
Time complexity The running time to find the convex polygon by using the Brute-force approach is O(.n3)
Brute-Force Strengths and Weaknesses Strengths wide applicability simplicity yields reasonable algorithms for some important problems (e.g., matrix multiplication, sorting, searching, string matching) Weaknesses rarely yields efficient algorithms some brute-force algorithms are unacceptably slow not as constructive as some other design techniques
Exhaustive Search A brute force solution to a problem involving search for an element with a special combinatorial objects such as permutations, combinations, or subsets of a set. Ex: Travelling Salesman Problem, Knapsack problem, Assignment Problem. property, usually among Method: generate a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far when search ends, announce the solution(s) found
