Java program: Convex Hull using Divide and Conquer Algorithm A convex hull is the smallest convex...
Java program:
Convex Hull using Divide and Conquer Algorithm
A convex hull is the smallest convex polygon containing all the given points.
Input is an array of points specified by their x and y coordinates. The output is the convex hull of this set of points.
Examples:
Input : points[] = {(0, 0), (0, 4), (-4, 0), (5, 0),
(0, -6), (1, 0)};
Output : (-4, 0), (5, 0), (0, -6), (0, 4)
use Divide and Conquer Algorithm
please explain the complexity and write good comments
Homework Answers
**Provided solution for both brute Force and divide & conquer.
Complexity:
Brute Force:o(n^3).
Divide and conquer:
The merging of the left and the right convex hulls take O(n) time and as we are dividing the points into two equal parts, so the time complexity of the below algorithm is O(n * log n).
- Worst case time complexity: Θ(N log N)
- Average case time complexity: Θ(N log N)
- Best case time complexity: Θ(N log N)
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ConvexHull
{
protected static final boolean IS_FIRST_HALF = true;
protected static final boolean IS_NOT_FIRST_HALF = false;
/**
* Basic idea: Given a set of points P, test each line segment
* to see if it makes up an edge of the convex hull.
*
* Complexity: O(n3)
*
* @param points a given set of points P
* @return the convex hull i.e a set of points
*/
public static List<Point> bruteForce(List<Point> points)
{
Set<LineSegment> lines = getAllPossibleLineSegment(points);
List<Point> pointsOnConvexHull = checkIfEachLineSegmentMakesAnEdgeOfConvexHull(points, lines);
return pointsOnConvexHull;
}
/**
* Basic idea: Finding the convex hull of small sets is easier than finding
* the hull of large ones.
*
* The first small set consists of half the points with the lowest x coordinates
* and the second small set consists of half the points with the highest x coordinates.
*
* Complexity: O(nlogn)
*
* @param points a given set of points P
* @return
*/
public static List<Point> divideAndConquer(List<Point> points)
{
Collections.sort(points);
List<Point> firstSmallSet = splitSet(points, IS_FIRST_HALF);
List<Point> secondSmallSet = splitSet(points, IS_NOT_FIRST_HALF);
List<Point> firstSetPointsOnConvexHull = bruteForce(firstSmallSet);
List<Point> secondSetPointsOnConvexHull = bruteForce(secondSmallSet);
sortPointsClockwiseOrder(firstSetPointsOnConvexHull);
sortPointsCounterClockwiseOrder(secondSetPointsOnConvexHull);
List<Point> pointsOnConvexHull = mergeHulls(firstSetPointsOnConvexHull, secondSetPointsOnConvexHull);
return pointsOnConvexHull;
}
/**
* Given a original set, split it by two, returning the first or second half.
*
* @param points a given set of points
* @param isFirstHalf a flag to check if it should return the first half of the subset
* @return
*/
protected static List<Point> splitSet(List<Point> points, boolean isFirstHalf)
{
if(isFirstHalf)
{
int setSize = points.size() / 2;
List<Point> smallSet = new ArrayList<Point>();
for (int i = 0; i < setSize; i++)
{
Point nextPoint = points.get(i);
smallSet.add(nextPoint);
}
points.removeAll(smallSet);
return smallSet;
}
return points;
}
/**
* Merges two convex hulls using the tangent method.
*
* @param firstConvexHull a convex hull
* @param secondConvexHull another convex hull
* @return mergedHull a set of points merging the two convex hulls
*/
private static List<Point> mergeHulls(List<Point> firstConvexHull, List<Point> secondConvexHull)
{
LineSegment lowerTangent = findLowerTangent(firstConvexHull, secondConvexHull);
LineSegment upperTangent = findUpperTangent(firstConvexHull, secondConvexHull);
List<Point> convexHull = getConvexHull(lowerTangent, upperTangent, firstConvexHull, secondConvexHull);
return convexHull;
}
/**
* Given the two convex hulls, with the first one containing the lowest x coordinates
* and the second contains the highest coordinates, given also the lower and upper tangent,
* returns a convex hull set of points by discarding the points between those two tangents.
*
* @param lowerTangent the lower tangent of the two convex hulls
* @param upperTangent the upper tangent of the two convex hulls
* @param firstConvexHull the first convex hull containing the lowest x coordinates points
* @param secondConvexHull the second convex hull containing the highest x coordinates points
* @return the convex hull merged
*/
private static List<Point> getConvexHull(LineSegment lowerTangent, LineSegment upperTangent, List<Point> firstConvexHull, List<Point> secondConvexHull)
{
List<Point> convexHull = new ArrayList<Point>();
for (Point point : firstConvexHull)
{
if(point.x() > upperTangent.a().x() || point.x() > lowerTangent.a().x())
{
if(point.y() < upperTangent.a().y() || point.y() > lowerTangent.a().y())
{
continue;
}
}
convexHull.add(point);
}
for (Point point : secondConvexHull)
{
if(point.x() < upperTangent.b().x() || point.x() < lowerTangent.b().x())
{
if(point.y() < upperTangent.b().y() && point.y() > lowerTangent.b().y())
{
continue;
}
}
convexHull.add(point);
}
return convexHull;
}
/**
* This method find the upper tangent. This method is symmetric to the lower tangent method.
*
* @param firstConvexHull the first convex hull containing the leftmost points
* @param secondConvexHull the second convex hull containing the rightmost points
* @return upperTangent the upperTangent between those two convex hulls
*/
protected static LineSegment findUpperTangent(List<Point> firstConvexHull, List<Point> secondConvexHull)
{
Point rightmostPointFirstConvexHull = getRightMostPoint(firstConvexHull);
Point leftmostPointSecondConvexHull = getLeftMostPoint(secondConvexHull);
LineSegment upperTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
Boolean isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(upperTangent, firstConvexHull, secondConvexHull);
while(!isEveryPointOnTheSameLine)
{
int leftmostPointSecondConvexHullIndex = secondConvexHull.indexOf(leftmostPointSecondConvexHull) ;
leftmostPointSecondConvexHullIndex = (leftmostPointSecondConvexHullIndex - 1) % secondConvexHull.size();
if(leftmostPointSecondConvexHullIndex < 0)
{
leftmostPointSecondConvexHullIndex+= secondConvexHull.size();
}
leftmostPointSecondConvexHull = secondConvexHull.get(leftmostPointSecondConvexHullIndex);
upperTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(upperTangent, firstConvexHull, secondConvexHull);
if(isEveryPointOnTheSameLine)
{
return upperTangent;
}
int rightmostPointFirstConvexHullIndex = firstConvexHull.indexOf(rightmostPointFirstConvexHull);
rightmostPointFirstConvexHullIndex = (rightmostPointFirstConvexHullIndex - 1) % firstConvexHull.size();
if(rightmostPointFirstConvexHullIndex < 0)
{
rightmostPointFirstConvexHullIndex+= firstConvexHull.size();
}
rightmostPointFirstConvexHull = firstConvexHull.get(rightmostPointFirstConvexHullIndex);
upperTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(upperTangent, firstConvexHull, secondConvexHull);
}
return upperTangent;
}
/**
* This method find the lower tangent using a simple walking procedure.
*
* @param firstConvexHull the first convex hull containing the leftmost points
* @param secondConvexHull the second convex hull containing the rightmost points
* @return lowerTangent the lowerTangent between those two convex hulls
*/
protected static LineSegment findLowerTangent(List<Point> firstConvexHull, List<Point> secondConvexHull)
{
Point rightmostPointFirstConvexHull = getRightMostPoint(firstConvexHull);
Point leftmostPointSecondConvexHull = getLeftMostPoint(secondConvexHull);
LineSegment lowerTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
Boolean isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(lowerTangent, firstConvexHull, secondConvexHull);
while(!isEveryPointOnTheSameLine)
{
int rightmostPointFirstConvexHullIndex = firstConvexHull.indexOf(rightmostPointFirstConvexHull);
rightmostPointFirstConvexHullIndex = (rightmostPointFirstConvexHullIndex + 1) % firstConvexHull.size();
rightmostPointFirstConvexHull = firstConvexHull.get(rightmostPointFirstConvexHullIndex);
lowerTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(lowerTangent, firstConvexHull, secondConvexHull);
if(isEveryPointOnTheSameLine)
{
return lowerTangent;
}
int leftmostPointSecondConvexHullIndex = secondConvexHull.indexOf(leftmostPointSecondConvexHull);
leftmostPointSecondConvexHullIndex = (leftmostPointSecondConvexHullIndex + 1) % secondConvexHull.size();
leftmostPointSecondConvexHull = secondConvexHull.get(leftmostPointSecondConvexHullIndex);
lowerTangent = new LineSegment(rightmostPointFirstConvexHull, leftmostPointSecondConvexHull);
isEveryPointOnTheSameLine = checkIfEveryPointIsOnTheSameSide(lowerTangent, firstConvexHull, secondConvexHull);
}
return lowerTangent;
}
/**
* Given a set of points P and a set of line segments,
* iterate over all line segments to check if it makes an edge of
* the convex hull.
*
* @param points a given set of points P
* @param lines a set of line segments
* @return a set of points that makes an edge of the convex hull
*/
private static List<Point> checkIfEachLineSegmentMakesAnEdgeOfConvexHull(List<Point> points, Set<LineSegment> lines)
{
List<Point> pointsOnConvexHull = new ArrayList<Point>();
for (LineSegment line : lines)
{
if(checkIfEveryPointIsOnTheSameSide(line, points))
{
Point a = line.a();
Point b = line.b();
if(!pointsOnConvexHull.contains(a))
{
pointsOnConvexHull.add(a);
}
if(!pointsOnConvexHull.contains(b))
{
pointsOnConvexHull.add(b);
}
}
}
return pointsOnConvexHull;
}
/**
* Given a set of points P, returns all possible line segments.
*
* @see https://en.wikipedia.org/wiki/Complete_graph
* @param points a given set of points P
* @return a set of line segments
*/
protected static Set<LineSegment> getAllPossibleLineSegment(List<Point> points)
{
Set<LineSegment> lines = new HashSet<LineSegment>();
for (Point point : points)
{
for (Point point2 : points)
{
if(point2.equals(point))
{
continue;
}
LineSegment line = new LineSegment(point, point2);
lines.add(line);
}
}
return lines;
}
/**
* Given a line segment and a set of points, check if every point is on the same side of the line segment.
* @param line a given line
* @param points a given set of points
* @return
*/
private static boolean checkIfEveryPointIsOnTheSameSide(LineSegment line, List<Point> points)
{
Boolean lastOrientation = null;
Boolean orientation = null;
for (Point point : points)
{
if(line.isPointOnLineSegment(point))
{
continue;
}
if(lastOrientation == null)
{
lastOrientation = point.isPointOnTheLeftOfLineSegment(line);
}
orientation = point.isPointOnTheLeftOfLineSegment(line);
if(!lastOrientation.equals(orientation))
{
return false;
}
lastOrientation = orientation;
}
return true;
}
/**
* Given a line segment and two set of points, check if every point (considering both sets) is on the same side of the line segment.
*
* @param line a given line segment
* @param firstConvexHull a set of points
* @param secondConvexHull another set of points
* @return true if every point is on the same side or false otherwise
*/
private static boolean checkIfEveryPointIsOnTheSameSide(LineSegment line, List<Point> firstConvexHull, List<Point> secondConvexHull)
{
Boolean lastOrientation = null;
Boolean orientation = null;
List<Point> points = new ArrayList<Point>(firstConvexHull);
points.addAll(secondConvexHull);
for (Point point : points)
{
if(line.isPointOnLineSegment(point))
{
continue;
}
if(point.isPointAlignedWithLineSegment(line))
{
continue;
}
if(lastOrientation == null)
{
lastOrientation = point.isPointOnTheLeftOfLineSegment(line);
}
orientation = point.isPointOnTheLeftOfLineSegment(line);
if(!lastOrientation.equals(orientation))
{
return false;
}
lastOrientation = orientation;
}
return true;
}
/**
* Sort a given set of points in clockwise order.
*
* @param points a given set of points
* @see http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
*/
protected static void sortPointsClockwiseOrder(List<Point> points)
{
Point centerPoint = getCenterPoint(points);
Collections.sort(points, new PointClockwiseComparator(centerPoint));
}
/**
* Sort a given set of points in counterclockwise order.
*
* @param points a given set of points
* @see http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
*/
protected static void sortPointsCounterClockwiseOrder(List<Point> points)
{
Point centerPoint = getCenterPoint(points);
Collections.sort(points, new PointCounterClockwiseComparator(centerPoint));
}
/**
* Computes the center of a given set of points.
*
* @param points a given set of points
* @return center a point which is the center of this point set.
* @see http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
*/
protected static Point getCenterPoint(List<Point> points)
{
double sumOfXCoordinates = 0.0;
double sumOfYCoordinates = 0.0;
for (Point point : points)
{
sumOfXCoordinates+= point.x();
sumOfYCoordinates+= point.y();
}
sumOfXCoordinates = sumOfXCoordinates / points.size();
sumOfYCoordinates = sumOfYCoordinates / points.size();
Point center = new Point(sumOfXCoordinates, sumOfYCoordinates);
return center;
}
/**
* Return the leftmost point in a list.
* @param points
* @return leftMost the leftMost point
*/
private static Point getLeftMostPoint(List<Point> points)
{
Point leftMost = null;
for (Point point : points)
{
if(leftMost == null)
{
leftMost = point;
}
if(point.x() < leftMost.x())
{
leftMost = point;
}
}
return leftMost;
}
/**
* Return the rightMost point of a given list.
* @param points
* @return rightMost the rightmost point of a list
*/
private static Point getRightMostPoint(List<Point> points)
{
Point rightMost = null;
for (Point point : points)
{
if(rightMost == null)
{
rightMost = point;
}
if(point.x() > rightMost.x())
{
rightMost = point;
}
}
return rightMost;
}
}
Add Answer to:
Java program:
Convex Hull using Divide and Conquer
Algorithm
A convex hull is the smallest convex...
Provide a divide-and-conquer algorithm for determining the smallest and second smallest values in a given unordered...
Provide a divide-and-conquer algorithm for determining the smallest and second smallest values in a given unordered set of numbers. Provide a recurrence equation expressing the time complexity of the algorithm, and derive its exact solution (i.e., not the asymptotic solution). For simplicity, you may assume the size of the problem to be an exact power of a the number 2
Provide a most efficient divide-and-conquer algorithm for determining the smallest and second smallest values in a...
Provide a most efficient divide-and-conquer algorithm for determining the smallest and second smallest values in a given unordered set of numbers. Provide a recurrence equation expressing the time complexity of the algorithm, and derive its exact solution in the number of comparisons. For simplicity, you may assume the size of the problem to be an exact power of a the number 2
GIFT WRAPPING ALGORITHM OF JARVIS MARCH In mathematics, the convex hull of a set of points...
GIFT WRAPPING ALGORITHM OF JARVIS MARCH In mathematics, the convex hull of a set of points is the smallest convex set that contains these points. The convex hull may be visualized as the shape enclosed by a rubber band stretched around these points (see the figure below). In your first homework, you are going to compute the convex hull of a set of given points in a separate file (input.txt). For the given set of 14 points below, you can...
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algo...
need help in this algorithm question
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algorithm that finds the two indices 1 sisjsn such that A[k] (the sum of the elements from i to j) is maximized. For example, in the array A [10,-5,-6,5, 7,-2,4, -11], the sub-array A[4:6] has the sum 5+ 7-2+4-14 and no other sub-array contains elements that sum to a value greater than 14, so for this input the...
1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array...
1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...
Divide and Conquer & Algorithm Design 5. (20 points) Consider the following algorithm Precondition: S is...
Divide and Conquer & Algorithm Design 5. (20 points) Consider the following algorithm Precondition: S is a sorted list index mystery (index low, index high, const Array S[], number x) if low S high then mid = (low + high) / 2 if x = Smid] then return mid elsif x < s[mid] then return mystery (low, mid-1, s, x) else return mystery (mid+1, high, s, x) else return 0 end What does the recursive algorithm above compute? Explain why?
Write a program in Java that performs the Counting Sort algorithm. a) Create the countingSort method....
Write a program in Java that performs the Counting Sort algorithm. a) Create the countingSort method. Use the pseudocode shown in the lecture. b) Test your codes by writing a program that uses the following input array: int[] array_A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2}; c) Your output should display the following versions of the arrays: I. The original input array A II. The counting array C after the counting (lines 4-5 in pseudocode)...
8. (1) Implement the minimum subsequence sum using divide-and-conquer. (30 points) (2) For the array =[4-3...
8. (1) Implement the minimum subsequence sum using divide-and-conquer. (30 points) (2) For the array =[4-3 5-2-1 2 6-2, you should provide the solution using the minimum subsequence sum like the example in class. Test the sample for your code. (3) Obtain the T(n) expression for the above algorithm
my question is on a java program. i have added all instructions for this homeowrk assignment....
my question is on a java program. i have added all instructions for this homeowrk assignment. from how the input is entered and what the output should read. im seeing if i can get a psuedo code setup for how the algorithm should be setup. Build an Intersection Check program. User inputs two points as x-y coordinates in twodimension space. Two points represent two end points of a line segment. Then, user can input second two points for the second...
GIFT WRAPPING ALGORITHM OF JARVIS MARCH In mathematics, the convex hull of a set of points is the smallest convex set that contains these points. The convex hull may be visualized as the shape enclosed by a rubber band stretched around these points (see the figure below). In your first homework, you are going to compute the convex hull of a set of given points in a separate file (input.txt). For the given set of 14 points below, you can...
need help in this algorithm question
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algorithm that finds the two indices 1 sisjsn such that A[k] (the sum of the elements from i to j) is maximized. For example, in the array A [10,-5,-6,5, 7,-2,4, -11], the sub-array A[4:6] has the sum 5+ 7-2+4-14 and no other sub-array contains elements that sum to a value greater than 14, so for this input the...
Divide and Conquer & Algorithm Design 5. (20 points) Consider the following algorithm Precondition: S is a sorted list index mystery (index low, index high, const Array S[], number x) if low S high then mid = (low + high) / 2 if x = Smid] then return mid elsif x < s[mid] then return mystery (low, mid-1, s, x) else return mystery (mid+1, high, s, x) else return 0 end What does the recursive algorithm above compute? Explain why?
8. (1) Implement the minimum subsequence sum using divide-and-conquer. (30 points) (2) For the array =[4-3 5-2-1 2 6-2, you should provide the solution using the minimum subsequence sum like the example in class. Test the sample for your code. (3) Obtain the T(n) expression for the above algorithm
Most questions answered within 3 hours.
-
In the context of the 55 principles, _________
means to keep a process going through training,...
asked 7 minutes ago -
Can you write a 400 words paragraph about investigation on
permeability of cell membrane for SDS,...
asked 8 minutes ago -
This question is regarding Computer Security;
What do you think are some other security risks and...
asked 16 minutes ago -
Assume that you work for an organization that has around 10,000
desktops/laptops and approximately 1,000 servers...
asked 23 minutes ago -
An electron moves along the z-axis with vz=5.2×10^7m/s.
As it passes the origin, what are the...
asked 26 minutes ago -
Silly-Sort(A,i,j)
if A[i] > A[j]
then exchange A[i] and A[j];
if i+1 >= j
then return;...
asked 30 minutes ago -
Discuss the major contributions of Max Weber in understanding
the society theoretically. [10]
asked 32 minutes ago -
The rate constant for a certain reaction is k =
8.50×10−3 s−1 . If the initial...
asked 43 minutes ago -
a 5.00 kg ball moving to the right at a velocity of + 2.00 m /...
asked 37 minutes ago -
A charged paint is spread in a very thin uniform layer over the
surface of a...
asked 40 minutes ago -
The lifetime of a physical mechanism is given as f(x) = {(c/x^2
if 1< x <...
asked 49 minutes ago -
Please help me with this problem below
What is wrong with the following code?
if income...
asked 58 minutes ago