A Lower Bound for Shallow Partitions

Wolfgang Mulzer, Daniel Werner

Let P be a planar n-point set. A k-partition of P is a subdivision of P into n/k parts of roughly equal size and a sequence of triangles such that each part is contained in a trian…