International Collegiate Programming Contest

Computational Geometry and Miscellany

This session focuses on computational geometry, with a few problems on common techniques we have not covered. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set

1. Pick-up Sticks (Note: the problem does not state it, but you may assume that at every step there are no more than 1000 top sticks, and that no sticks intersect at an endpoint. You may wish to use fast I/O in this problem.)
2. It's not a Bug, it's a Feature! (Note: Efficiency is key in this problem. Keep that in mind if you are getting TLE.)
3. Nails* (Note: Be warned that intermediate operations may overflow 32 bit integers.)
4. Sunny Mountains
5. Trees on My Island
6. Together with your team, code up a working solution to Line and Circle Maze (from the first Team Practice).

A PDF containing all the problems is available here.

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

Basic Geometry

Before beginning to work on geometry problems, it is worth familiarizing yourself with some basic tools. This Topcoder tutorial has some information. One 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 somehing 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.

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.

Bitmasks

Moving away from geometry, let's discuss a useful, but perhaps not easily categorized, tool: using bitmasking to manipulate small sets. Bitmasks allow you to easily store, manipulate, and check membership in small sets simply by using integers, rather than large Boolean arrays. The idea is that the binary representation of a number gives you, for each i, whether the i-th element is in your set or not (by checking if the i-th least significant bit is 1). A lot of common set operations are then easily done with bitwise operations: for instance, to check if a set is nonempty, just check if the integer evaluates to true, to find intersection, union, symmetric difference, and complement you can use bitwise AND, OR, XOR, and complement respectively. The bitshift operators are often useful as well, if nothing else than for constructing the set containing only the i-th element for use in testing whether a set contains that element. Keep in mind that the interaction of the right bitshift operator with the sign bit is compiler-dependent, so it is a good idea use unsigned integers if you will be right-shifting.

If you are finding that you want to loop over a relatively small array of Booleans, store some state as an array of Booleans, or manipulate subsets of a small set, think about whether using this technique can make your code easier or your algorithm faster. Bitmasks can also be used in state-space search to make the encoding and manipulation of states eaiser.