Journal of Computational Geometry