This special issue of Discrete & Computational Geometry contains a selection of the best papers that were presented at the 32nd Annual ACM Symposium on Computational Geometry, which was held in Boston, USA, on June 14–17, 2016. The nine papers in this special issue were invited, submitted, reviewed, and revised according to the usual high standards of this journal. It is our pleasure to briefly introduce these contributions.

Eyal Ackerman, Balázs Keszegh and Mate Vizer consider the question of whether for a given finite set S of points in the plane and a geometric object Q, there is a constant m such that the points of S can be colored red and blue so that any homothet of Q that contains at least m points of S will contain a red point and a blue point. The main result is that such a constant exists when Q is a parallelogram.

Hugo Akitaya, Greg Aloupis, Jeff Erickson and Csaba Tóth present an \(O(n \log n)\) time algorithm to determine whether a polygon with n vertices is weakly simple. This improves the previous running time of \(O(n^2 \log n)\) time presented by Hsien-Chih Chang, Jeff Erickson and Chao Xu at SODA’15.

Sarah Allen, Luis Barba, John Iacono and Stefan Langerman discuss the amortized number of combinatorial changes needed to update a Voronoi diagram of a set of n sites in the plane, as the sites are added to the set. For a newly defined update operation, they show that the amortized cost is \(O(\sqrt{n})\) (where cost is the minimum number of edge insertions and removals needed). They also present an output-sensitive data structure that maintains the nearest- or farthest-point Voronoi diagram of a set S of n points in convex position as new points are added to S.

Sunil Arya, Guilherme da Fonseca and David Mount consider the problem of approximating convex bodies in high dimension. Earlier work established that a body could be \(\varepsilon \)-approximated by a polytope with \(O(\varepsilon ^{(d-1)/2})\) facets, or vertices, but the bounds for the total combinatorial complexity of the polytope were much larger. This paper establishes this bound, with some additional polylogarithmic factors, by constructing a polytope with this total complexity.

Benjamin Burton, Arnaud de Mesmay and Uli Wagner study the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated3-manifold. The authors prove that the problem is NP-hard. When the genus is odd, the problem lies in NP, and an explicit algorithm is given.

Hsien-Chih Chang and Jeff Erickson study the minimal number of homotopy moves needed to transform any planar curve with n self-intersections into a simple curve. They prove that \(O(n^{3/2})\) moves are always sufficient and that this bound is tight, as some curves require \(\mathrm{\Omega }(n^{3/2})\) moves to be simplified. This improves the previously best known \(O(n^2)\) upper bound, already implicit in Steinitz’s work.

Alfredo Hubard, Vojtěch Kaluža, Arnaud de Mesmay and Martin Tancer pursue a question that generalizes Fary’s theorem about the straight-line embedding of any planar graph into the Euclidean plane: Can a surface S be assigned a “universal metric” such that every graph embeddable onto S can be drawn by a shortest path embedding? They show that this is true for a variety of surfaces of low genus, but trickier for higher genus.

Benjamin Raichel and C. Seshadhri present a new algorithm for constructing the contour tree of a piecewise linear map on a simplicial complex. The main feature of this new algorithm is that the running time avoids global sorting of the critical vertices and instead depends on path decompositions of the contour tree. The running time is proved to be bounded by a certain implicit path decomposition; these results are optimal in terms of how much sorting has to be done by any algorithm on a specific terrain.

Orit Raz proves some new characterizations of rigidity and global rigidity of graphs in terms of a kind of realization space of the graph as (a subgraph of) an intersection graph of lines in \(\mathbb C^3\). These results generalize and simplify some important results in rigidity theory.

We thank our anonymous referees for their careful diligence in reviewing the papers in this special issue, and we thank the authors for their contributions and revisions.