Scribd
Upload
16 views3 pages

Data Structure and Algorithm

The document discusses the differences between the Closest Pair Problem and the Convex Hull Problem in computational geometry, highlighting their goals and brute force approaches. The Closest Pair Problem aims to find the two closest points in a 2D plane with a time complexity of O(n^2), while the Convex Hull Problem seeks to identify the smallest convex polygon enclosing a set of points with a time complexity of O(n^3). It also provides examples for both problems, including scenarios involving wildlife tracking and city boundary mapping.

Uploaded by

nutwjdf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views3 pages

Data Structure and Algorithm

The document discusses the differences between the Closest Pair Problem and the Convex Hull Problem in computational geometry, highlighting their goals and brute force approaches. The Closest Pair Problem aims to find the two closest points in a 2D plane with a time complexity of O(n^2), while the Convex Hull Problem seeks to identify the smallest convex polygon enclosing a set of points with a time complexity of O(n^3). It also provides examples for both problems, including scenarios involving wildlife tracking and city boundary mapping.

Uploaded by

nutwjdf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Data Structure and Algorithm

Assignment #01 – Finals

Name: Naguit, Hurjay Ali D.


Section: BSIT – 2I
Date: 2025-04-01

1. Explain what is the difference between Closest


Pair and Convex Hull Problem in brute force.

Both the Closest Pair Problem and the Convex Hull Problem are
fundamental computational geometry problems, but they have different
objectives and brute force approaches.

a. Closest Pair Problem


 Goal: Find the two closest points from a given set of points in a 2D
plane.
 Brute Force Approach:
o Compare every pair of points.
o Calculate the Euclidean distance between each pair.
o Track the smallest distance found.
 Time Complexity: O(n2)O(n^2)O(n2) since we check all (n2)\binom{n}{2}
(2n) pairs.

b. Convex Hull Problem


 Goal: Find the smallest convex polygon (hull) that encloses all given
points.
 Brute Force Approach:
o Check every possible pair of points to see if they form an edge
of the convex hull.
o Ensure all other points lie on the same side of the edge.
 Time Complexity: O(n3)O(n^3)O(n3) in a brute force approach, as it
involves checking all triplets of points.
2. Give 2 examples per problem.
A. Closest Pair Problems
Example 1: Wildlife Tracking
Scientists track bird movement. Birds were spotted at (2,3), (12,30),
(40,50), (5,1), (12,10), and (3,4). Which two birds are closest?
Solution:
 Compute distances:
o (2,3) & (3,4): √[(3−2)² + (4−3)²] = √2 ≈ 1.41
 Answer: Closest birds are (2,3) and (3,4) with 1.41 distance.
Example 2: Security Cameras
A shopping mall installs security cameras at (-5,-5), (-6,-6),
(20,30), (15,15). The security system needs to identify the two
closest cameras to adjust coverage.
Solution:
 Compute distances:
o (-5,-5) & (-6,-6): √[(−6+5)² + (−6+5)²] = √2 ≈ 1.41
 Answer: Closest cameras are (-5,-5) and (-6,-6) with 1.41
distance.

B. Convex Hull Problem


Example 1: City Boundary Mapping

A city council wants to mark the boundaries of a city using GPS points: (2, 2), (3,
6), (5, 3), (7, 7), (8, 2), and (6, 4). They need to find the convex hull to
determine the city's outer limits.

Solution:

 The convex hull consists of the points forming the outer boundary of the city:

o The points forming the convex hull are (2,2), (3,6), (7,7), (8,2).

o The other points (5,3) and (6,4) are inside and are not part of the
convex hull.

Example 2: Mountain Range Exploration

Explorers want to mark the boundary of a mountain range based on their survey
points: (0,0), (2,1), (3,4), (1,3), (5,5), and (4,2). They need to find the convex
hull to outline the range.

Solution:
 The convex hull consists of the outermost points:

o The points forming the convex hull are (0,0), (2,1), (3,4), (5,5).
o The points (1,3) and (4,2) lie inside the convex hull.

You might also like