Swedish web site
AAPS Advanced Algorithmic Problem Solving
Lab 4
Lab Assignment 4
The recommended deadline for lab 4 is 2014-05-12 kl 12:00
Read the general instructions before you start.
The suggested API below is pseudo code, you have to translate it to your favorite language in an appropriate way.
The "recommended time complexity" is what is required to pass the time requirements in Kattis. In case the task is to implement a specific algorithm you may implement any algorithm which has the same or better time complexity.
Advice: In both C++ and Java it is practical to use iterators to represent vectors, sets etc.
Task 4.1: Point Class
No Kattis problem.
Implement a class for 2 dimensional points which can also be interpreted as mathematical vectors. The class should at least support:
- Point wise addition/subtraction
- Multiplication/division with scalar
- Scalar product
- Cross product
- Distances and angles of a vector and between points
Task 4.2: Polygon Area (1p)
Kattis problem: polygonarea
Write a method computing the area of a (simple) polygon.
Suggested API:
double polygon_area(point[])
Recommended time complexity: O(n), where n is the number of points in the polygon.
Task 4.3: Point in Polygon (1p)
Kattis problem: pointinpolygon
Write a method determining whether a point is inside, on the border or outside a (simple) polygon.
Suggested API:
int inside_poly(point p, point[] poly)
where the function returns -1, 0 or 1 depending on whether the point is outside, on the border or inside the polygon.
Recommended time complexity: O(n), where n is the number of points in the polygon.
Task 4.4: Intersection of Line Segments (1p)
Kattis problem: segmentintersection
Write a method that finds the intersection between two line segments. The methods should be able to identify if no such intersection exists, whether it is a point, or whether it is a line segment (i.e., the two line segments are parallel and overlapping).
Suggested API:
point[] intersect(pair
where the returned vector has 0, 1 or 2 elements depending on whether no intersection exists, the intersection is a point or it is a line segment.
Task 4.5: Distance between Line Segments (1p)
Kattis problem: segmentdistance
Write a method that computes the distance between two line segments, i.e., the shortest distance between any point on the first line segment and any point on the second line segment.
Suggested API:
double segment_dist(pair
Task 4.6: Point Sets - Closest Pair of Points - Average Case (1p)
Kattis problem: closestpair1
Write a method for finding a pair of points with minimal distance in a set of points. The expected run time should be O(n log n) under the assumption that the points are uniformly distributed in a sub square of R2. You do not have to prove that your algorithm has the expected run time.
Suggested API:
int[2] closest_pair(point[])
where the method returns the indexes for a pair of points with minimal distance between them.
Recommended time complexity: The expected run time should be O(n log n), where n is the number of points in the polygon, under the assumption that the points are uniformly distributed in a sub square of R2.
Task 4.7: Point Sets - Closest Pair of Points - Worst Case (1p)
Kattis problem: closestpair2
Write a method for finding a pair of points with minimal distance in a set of points. The worst case run time should be O(n log n).
Suggested API:
int[2] closest_pair(point[])
where the method returns the indexes for a pair of points with minimal distance between them.
Recommended time complexity: O(n log n), where n is the number of points.
Task 4.8: Point Sets - Convex Hull (1p)
Kattis problem: convexhull
Write a method computing the convex hull of a set of points. The method should handle degenerated point sets, i.e., where all points are on a line.
Suggested API:
point[] convex_hull(point[])
where the method returns an array with the points on the border of the hull ordered either clockwise or counter clockwise. It can sometimes be more efficient to return an array of integers with the indexes of the points on the border of the hull.
Recommended time complexity: O(n log n), where n is the number of points.
Task 4.9: Point Sets - Maximal Set of Colinear Points (1p)
Kattis problem: maxcolinear
Write a method that computes the maximal set of colinear points in a set of points, i.e., a set of points on the same straight line. It is enough to find the maximal number of points in the set.
Suggested API:
int number_of_colinear(point[])
Recommended time complexity: Significantly better than Ω(n3), where n is the number of points.
Task 4.10: Linear Recurrences (1p)
Kattis problem: linearrecurrence
Write a method that solves linear recurrences.
Page responsible: Fredrik Heintz
Last updated: 2015-04-27
