We show that the planar dual to the Euclidean farthest point Voronoi diagram for the set of vertices of a convex polygon has the lexicographic minimum possible sequence of triangle angles, sorted from sharpest to least sharp. As a consequence, the sharpest angle determined by three vertices of a convex polygon can be found in linear time.

We describe algorithms for finding the k shortest paths connecting a given pair of vertices in a digraph (allowing cycles). Our algorithms output an implicit representation of the paths as an unordered set in time O(m + n log n + k). The paths can be output in order by length in total time O(m + n log n + k log k). We can also find the k paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn).

We perform linear programming optimizations on the intersection of k polyhedra in R^3, represented by their outer recursive decompositions, in expected time O(k log k log n + [square root of] k log k log^3 n). We use this result to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, we describe an improved solution to the planar 2-center and 2-median problems.

We show that for any edge-weighted graph G there is an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. The equivalent graph can be constructed in the time O(m + n log n) given a single minimum spanning tree of G. As a consequence we can count the minimum spanning trees of G in time O(m + n^2.376), generate a random minimum spanning tree in time O(mn), and list all minimum spanning trees in time O(m + n log n + k) where k denotes the number of minimum spanning trees generated. We also discuss similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

A convex polygon with n sides can be triangulated by O(n^1.85) triangles, without any obtuse angles. The construction uses a novel form of geometric divide and conquer.

We compute the k smallest spanning trees of a point set in the planar Euclidean metric in time O(n log n log k + k min(k, n )^1/2 log(k/n)), and in the rectilinear metrics in time O(n log n + n log log n log k + kmin(k,n)^1/2 log(k/n)). In three or four dimensions our time bound is O(n^4/3+c + k min(k, n)^1/2 log(k/n)), and in higher dimensions the bound is O(n^2-2([d/2]+1)+c + kn^1/2 log n).

We survey results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.

We use Mathematica to construct zonotopes and display zonohedra.

Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.

We show how to pack a non-simple polygon with O(n) tangent circles, so that each remaining region is adjacent to at most four circles, in total time O(n log n). This improves a previous O(n log^2 n) bound. As a consequence, we can triangulate the polygon with right and acute triangles in the same bounds.