Journal and book chapter submissions
Fast Schulze voting using quickselect.
A. Arora,
D. Eppstein, and
R. L. Huynh.
arXiv:2411.18790.
We show how to determine the outcome of a Schulze method election, from an input consisting of an \(m\times m\) array of pairwise margins of victory, in time \(O(m^2\log m)\). The algorithm uses random pivoting like that of quickselect.
Better late than never: the complexity of arrangements of polyhedra.
B. Aronov,
S. W. Bae,
O. Cheong,
D. Eppstein,
C. Knauer, and
R. Seidel.
41st European Workshop on Computational Geometry (EuroCG 2025),
Liblice, Czech Republic, pp. 62:1–62:4.
arXiv:2506.03960.
My 1994 paper "On the number of minimal 1-Steiner trees" with Aronov and Bern, in some preliminary manuscript versions, included a bound of \(O(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor})\) on the complexity of an arrangement of \(m\) convex polytopes given as intersections of a total of \(n\) halfspaces, interpolating between the upper bound theorem for polytopes and the complexity of hyperplane arrangements. However, the manuscript and the proof were lost. This paper re-proves the result, with better care for the degenerate cases.
Entropy-bounded computational geometry made easier and sensitive to sortedness.
D. Eppstein,
M. T. Goodrich,
A. M. Illickan, and
C. A. To.
arXiv:2508.20489.
Proc. 37th
Canadian Conference on Computational Geometry, 2025,
pp. 53–61.
We define a notion of structural entropy of point sets under which a set has low entropy when it can be covered by few disjoint triangles that are either entirely under the hull of the input or presorted, and show that we can find the hull in time sensitive to this entropy. Generalizations of the same technique apply to geometric maxima, lower envelopes, and visibility polygons.