Algorithm Engineering and Experiments (ALENEX)
I was program co-chair for 2015.Lazy algorithms for dynamic closest pair with arbitrary distance measures.
J. Cardinal and D. Eppstein.
Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004, pp. 112–119.We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.
Quadratic time algorithms appear to be optimal for sorting evolving data.
J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
arXiv:1805.05443.We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.
Grid peeling and the affine curve-shortening flow.
D. Eppstein, S. Har-Peled, and G. Nivasch.
arXiv:1710.03960.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 109–116.
Experimental Mathematics 29 (3): 306–316, 2020.We conjecture, based on experiments, that approximating a convex shape by the set of grid points inside it, for a fine enough grid, and then finding the convex layers of the resulting point set, produces curves that are close to those produced by affine curve-shortening, a continuous process on smooth curves.