International Collegiate Programming Contest

Computational Geometry

This session focuses on computational geometry. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set (#4)

1. Intersecting Lines
2. Soya Milk
3. SCUD Busters
4. Trash Removal

Note: All problems expect I/O to be done using standard input and standard output. The solution to problems must be written in a single file. If you are programming in Java the application class should be called "Main".

Resources

Geometry problems often can be solved much more easily with appropriate library code. If you do not have implementations of the most commonly needed functions, we recommend taking a look at our library code at the following location: https://github.com/atmorgan/ICPC2014. In particular, we have the following files:

• Vector.cc - Defines point primitive and distance, cross, and dot products.
• PlaneGeometry.cc - Includes point, line, line segment, and circle intersection, projection, and collinearity tests (the pseudocode for distance from a point to a line segment on the placement test was taken adapted from this file).
• Polygon.cc - Provides functions for polygon area, perimeter, centroid, winding number, and convex hull.

Basic Geometry

Before beginning to work on geometry problems, it is worth familiarizing yourself with some basic tools. It is highly recommended to begin thinking of things in terms of dot products and cross products. The following top coder tutorial discusses these primitives.

Another basic problem in computational geometry is to determine whether two (or more) line segments intersect. This page has a nice overview of this problem, though it should be read in conjunction with notes for the later sections.

Do not overuse the trig and inverse trig functions, as they can slow down your program and introduce precision errors if you use them where it isn't necessary. The usual recommendation to use integer rather than floating-point arithmetic where possible still stands; though in geometry problems you will often find yourself using floating point numbers, you might not have to as much as you think if the inputs are integers.

Convex Hull

One basic problem in plane geometry is finding the convex hull of a set of points. Recall that a convex region is a region such that any line segment connecting two points of the region is contained entirely within the region. The convex hull of a set of points, then, is the smallest convex region containing all the points. Since for most purposes, we're interested in points defining the boundary of that region, we will often denote by the "convex hull" of a finite set of points the subset of those points which are vertices of the boundary of the actual convex hull. That is, the "convex hull" consists of the vertices of the smallest convex polygon such that every point of the set is either inside or on the boundary of the polygon.

Convex hull problems often involve things like perimeter (the polygon formed by the convex hull has minimum perimeter among all regions containing all the points), enclosing area, convexity, and other similar geometric notions. Also, finding the convex hull can sometimes be useful in other places, e.g., to reduce the number of points that need to be taken into consideration for further processing.

One relatively easy-to-implement algorithm for finding convex hull is called Graham Scan. A succinct outline of Graham Scan can be found on the Wikipedia page here. It runs in O(n log n) time. It is worth noting that you never actually need to compute any angles; all the sorting and testing can be done by computing signs of various cross products. Another well-known algorithm is Jarvis' walk, also known as gift-wrapping.

Polygon Area

A polygon can be viewed as a sequence of line segments, or as the area inscribed by them, or as the sequence of endpoints of these line segments (the vertices of the polygon). A polygon is called simple if the line segments to not intersect.

There are two very useful formulas for the area of a simple polygon, given its vertices in order (either clockwise or counterclockwise). The first is a general formula, based on the fact that the signed area of a plane triangle is equal to one half the cross product of two of its edges. If we add this up over all triangles obtained by adjacent vertices in the polygon, we get A = (1/2)sum(i=1..n : x_i-1y_i - x_iy_i-1), where p_i = (x_i, y_i) are the vertices of the polygon, p₀ = p_n, given in clockwise or counterclockwise order. The area will be negative if the order is clockwise and positive if the order is counterclockwise.

When the coordinates of all vertices are integer, there is another nice formula for the area of a simple polygon -- Pick's Theorem. This theorem states that the area of a simple polygon with vertices only on the lattice of points with intger coordinates, is equal to the number of lattice points in its interior, plus half the number of lattice points on its boundary, minus 1. When a problem involves lattice polygons, you might think about how you can use this theorem.

Sweep Lines

The notion of a sweep line is a general idea that may be used to make many geometric problems tractable. The idea is to pass a changing line over the plane (or in general a surface through space) and do something whenever it passes a critical point of the problem. This allows a seemingly global problem to be somewhat localized; you need only keep track of what points the sweep line is currently passing through plus whatever cumulative information you've already computed, rather than navigate everything in the global problem at once. The sweep line can be vertical or horizontal, moving parallel to an axis, or it can rotate about a fixed point.

Though one imagines the sweep line moving smoothly as it covers the area of the problem, with the algorithm doing something whenever the sweep line intersects a critical point, in fact one first sorts all the critical points and iterates over them. A primer on line sweep algorithms is available at this Topcoder tutorial (updated link for 2015).

Line sweep algorithms are not just for geometry! Indeed, many kinds of interval algorithms can be thought of as line sweep algorithms (for instance, determining the clique number of an interval graph). If you can focus your attention on certain critical points, and do all your work as some local work at each critical point plus some cumulative information, then the line sweeping idea may apply.