Paper ID: 2311.05651

On Mergable Coresets for Polytope Distance

Benwei Shi, Aditya Bhaskara, Wai Ming Tai, Jeff M. Phillips

We show that a constant-size constant-error coreset for polytope distance is simple to maintain under merges of coresets. However, increasing the size cannot improve the error bound significantly beyond that constant.

Submitted: Nov 8, 2023