Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 1, March 2017

Section: Computational Geometry

Instance-Optimal Geometric Algorithms
Peyman Afshani, Jérémy Barbay, Timothy M. Chan
Article No.: 3
DOI: 10.1145/3046673

We prove the existence of an algorithm A for computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A′ in a...

Section: Computational Geometry

Amplifiers for the Moran Process
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby
Article No.: 5
DOI: 10.1145/3019609

The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one...