CS345 Algorithms Assignment 1 Solution: Convex Hull and FFT

This document presents a comprehensive solution to an algorithms assignment, addressing key concepts in computational geometry and algorithm analysis. The solution begins by defining a unit square and its properties, followed by a detailed explanation of a convex hull algorithm, including how to combine two convex hulls and the recursive approach to solving the problem. It delves into linear combinations and convex hull properties, providing insights into the relationships between points and their linear spans. The solution also covers time complexity analysis for a specific algorithm, demonstrating how to determine the efficiency of the algorithm. Finally, the document tackles a problem involving the Cartesian sum of sets and leverages the Fast Fourier Transform (FFT) to optimize the solution, offering a detailed explanation of the FFT's application in this context. The document includes references to relevant academic literature, providing a robust and well-supported solution to the assignment.

1
Algorithms
ALGORITHMS
By Student's Name
Course Code and Name
Professor’s Name
University Name
City, State
Date of Submission

2
ALGORITHMS
Question 1
A unit square is a square that has uniform sides. Usually it denotes precisely to the Cartesian
plane square with four points. The unit square in a Cartesian coordinate system with
coordinates (x, y) comprises of points where both y and x are positioned in a unit that is
closed from zero to one. IX1 is the Cartesian product of a unit.
In this case, I represents the unit interval that is closed. Therefore, in our case 0.7 is the
interval. Thus, I represents the closed unit interval.
Question 2
Given the following input: points [ ] = {(0,0), (0,4), (-4,0), (5, 0), (0,-6), (1,0)
Provided with the set of points that we have to get the convex hull. Assume we are conscious
the left half points convex hull, and then the challenge presently is to combine the 2 convex
hulls and establish the convex hull for the complete set. This can be achieved by getting the
lower and upper tangent to the left and right convex hulls. This is indicated below by
Tangents between 2 convex polygons. 1. (Chazelle, An Optimal Convex Hull Algorithm For
Points Sets In Any Fixed Dimension (Princeton University, Dept. of Computer Science,
1991).
Let the right convex hull be b and the left convex hull be a. Then the upper and lower
tangents are identified as 1 and 2 correspondingly, as indicated in the figure below

3
ALGORITHMS
Presently, the challenge continues to be, how to get the convex hull for the right and left half.
Here recursion comes in handy; we split the set of points until when the set’s total points
minimal, for instance five and we can get this point’s convex hull through the brute force
algorithm. The combining of these halves would lead to a convex hull for the set of points
that are complete.

4
ALGORITHMS

5
ALGORITHMS

6
ALGORITHMS

7
ALGORITHMS
After the convex hull computation, the output of the problem given is :(-4, 0), (5, 0), (0, -6),
(0, 4)
The output indicates that after computing the output, the output is sorted in a certain order,
thus proving the problem.
Question 3
i) Consider S C R^2
lin(S) := q q = =∑λipi ∧ ∀ i : pi ∈ S, λi ∈ R

8
ALGORITHMS
Linear unique convex hull is the set of all linear combinations of S (minimum linear subspace
comprising S). For example, if S = {p} C R^2OR {0} then lin (S) is the line through p and
the origin (Eddy, W.F., 2017)
ii) Assume S to be a set of 4 instants in a position that is general. In case S is not in a position
of convex, we plot the outer face vertices of G to the 3 positions on S’s convex hull. In all
scenarios, the vertices that are pending are sketched inside the convex hull of S, through
utilizing the 4th position of S to put one of them. In case the positions of S are in a point of
convex, let s1, s2, s3, s4, s5 be positions of CH (S) in a manner that is clockwise. Allow s5
together s6 be positions not in S so that triangle s1, s5, s6 consists S \ {s1} in its interior, s5
visualizes s3, s4, s2 and s1 in clockwise manner; and s6 visualizes s3, s4, s2 and s1in an order
that is counterclockwise. Surely, it is right to substantiate that such positions subsist because
S is in a position of convex.
Question 4
Input: A series of positions P = {p1…..p}
Begin
h = {p1}
k= 1
For i =2 to n do
If p1 is not controlled by any point in R then
k=k+1
Insert p1 at the end of h
M= {pjk}

9
ALGORITHMS
For i =k-1 downto 1 do
If pji nod dominated by any point in M insert pji in M
end
The time complexity becomes O(n log h) time.
Question 5
The first step is to comprehend the problem. A together with B each has n elements that can
be arranged from o to 10n. C is the Cartesian sum of sets A and B, thus by explanation for the
set given before it has numerous as n^2 elements
For a in set X
For b in set Y
Insert into set C ( a+ b )
The answer to the problem rests in spotting the problem’s analogy with that of fast-fourier
transform (FFT). FFT offers us a means to multiply 2 polynomials of degree –bound n in O
(n log n) period instead of the brute force O (n^2) procedure for multiplying the two
polynomials.
Thus, we start by creating a polynomial A of degree 10n as shown below
A(x) = \Sum_{i=0}^{10n-1} a_i x^ i
Correspondingly, create set B
We can multiply the 2 polynomials in a period of O (n log n). The non-zero coefficient of the
terms are the frequency of the elements in C, and the power of the non-zero-coefficient terms
are the elements of C

10
ALGORITHMS

11
ALGORITHMS References List
1. Chazelle, B, An Optimal Convex Hull Algorithm For Points Sets In Any Fixed
Dimension(Princeton University, Dept. of Computer Science, 2011)