On Mergable Coresets for Polytope Distance

Abstract

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.

arXiv commentPresented in SoCG'19 Young Researchers Forum (CG:YRF)