What constitutes cheating on programming assignments? What methods can be used to detect cheating? What should be done with offenders? How can cheating be eliminated in programming courses? These are all pertinent questions, but they are directed more towards treating symptoms rather than towards correcting some very fundamental problems.

We develop optimal algorithms for forming the intersection of geometric objects in the plane and apply them to such diverse problems as linear programming, hidden-line elimination, and wire layout. Given N line segments in the plane, finding all intersecting pairs requires O(N2) time. We give an O(N log N) algorithm to determine whether any two intersect and use it to detect whether two simple plane polygons intersect. We employ an O(N log N) algorithm for finding the common intersection of N half-planes to show that the Simplex method is not optimal. The emphasis throughout is on obtaining upper and lower bounds and relating these results to other problems in computational geometry.

We employ elementary results from the theory of several complex variables to obtain a quadratic lower bound on the complexity of computing the mean distance between points in the plane. This problem has 2N inputs and a single output and we show that exactly N(N-1)/2 square roots must be computed by any program over +, -, ×, ÷,) √, log and comparisons, even allowing an arbitrary field of constants. The argument is based on counting the total number of sheets of the Riemann surface of the analytic continuation to the complex domain of the (real) function computed by any algorithm which solves the problem. While finding an exact answer requires O(N2) operations, we show that an ε-approximate solution can be obtained in O(N) time for any ε ≫ 0, even if no square roots are permitted.

We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem on N points in k−1 dimension. Special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.

A number of seemingly unrelated problems involving the proximity of N points in the plane are studied, such as finding a Euclidean minimum spanning tree, the smallest circle enclosing the set, k nearest and farthest neighbors, the two closest points, and a proper straight-line triangulation. For most of the problems considered a lower bound of O(N log N) is shown. For all of them the best currently-known upper bound is O(N2) or worse. The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space. The Voronoi diagram is used to obtain O(N log N) algorithms for all of the problems.

The complexity of a number of fundamental problems in computational geometry is examined and a number of new fast algorithms are presented and analyzed. General methods for obtaining results in geometric complexity are given and upper and lower bounds are obtained for problems involving sets of points, lines, and polygons in the plane. An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.