Closest Pair and Convex Hull: Brute Force Approach
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
