"We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. …"

"We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a non-convex environment. To handle arbitrary non-convex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise "gossip" communication. The algorithm has two components: (1) a motion protocol to ensure that neighboring robots communicate at least sporadically, and (2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, we detail how our algorithm scales well for large teams in large environments and how the computation can run in anytime with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system."

"Given a set $P$ of $n$ points in the plane, we solve the problems of constructing a geometric planar graph spanning $P$ 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set $P$, respectively. First, we construct in $O(nlog{n})$ time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in $O(nlog n)$ time a 2-edge connected geometric planar graph spanning $P$ with max edge length bounded by $sqrt{5}$ times the optimal, assuming that the set $P$ forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in $O(n^2)$ time. We also show that for $k in O(sqrt{n})$, there exists a set $P$ of $n$ points in the plane such that even though the Unit Disk Graph spanning $P$ is $k$-vertex connected, there is no 2-edge connected geometric planar graph spanning $P$ even if the length of its edges is allowed to be up to 17/16."

"We describe computer algorithms that produce the complete set of isohedral tilings by n-omino or n-iamond tiles in which the tiles are fundamental domains and the tilings have 3-, 4-, or 6-fold rotational symmetry. The symmetry groups of such tilings are of types p3, p31m, p4, p4g, and p6. There are no isohedral tilings with symmetry groups p3m1, p4m, or p6m that have polyominoes or polyiamonds as fundamental domains. We display the algorithms' output and give enumeration tables for small values of n.…"

"For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general p we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number p, we give algorithms that find the solution in the following running times:
For squares we have O(n+k log k) time for p=1, and O(n log n+k^p log^p k time for p = 2,3. For rectangles we get O(n + k^3) for p = 1 and O(n log n+k^{2+p} log^{p-1} k) time for p = 2,3. In all cases, our algorithms use O(n) space."

Bezier curves.

"We show that there is a straightforward algorithm to determine if the polyhedron guaranteed to exist by Alexandrov's gluing theorem is a degenerate flat polyhedron, and to reconstruct it from the gluing instructions. The algorithm runs in O(n^3) time for polygons of n vertices."

"We have described three types of geometric object that have natural encodings as regular labelings of a maximal or near-maximal planar graph. Although much about these labelings is known, there are still many questions remaining:…"

"This is the beginning of a project1 to record open problems of interest to researchers in computational geometry and related fields. It commenced with the publication of thirty problems in Computational Geometry Column 42 [MO01] (see Problems 1-30), but has grown much beyond that. We encourage correspondence to improve the entries; please send email to TOPP@cs.smith.edu. If you would like to submit a new problem, please fill out this template."

"We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. "

Let's just go ahead and tag this -- there is too much good stuff in here to indicate them individually. Chazelle's a geometry guy, and this has good things on: range-searching, nearest-neighbor stuff, polyhedral decomposition, and ... bird flocking. (recently.)

Bernard Chazelle's 1980 thesis, including decompositions of polyhedra.

"Mesh is a library for creating Voronoi, Delaunay and Convex Hull diagrams in Processing. After searching online for a Java package for creating Voronoi diagrams and failing to find anything simple enough to fit my needs I decided to make my own as simple as possible. I did find the wonderfully useful QuickHull3D package, which the algorithms for creating these diagrams are based on. These complete in O(n log n) time."

Michiel Smid's research publications on computational geometry and "geometric spanners."