On Mergable Coresets for Polytope Distance
- Resource Type
- Working Paper
- Authors
- Shi, Benwei; Bhaskara, Aditya; Tai, Wai Ming; Phillips, Jeff M.
- Source
- Subject
- Computer Science - Computational Geometry
Computer Science - Data Structures and Algorithms
Computer Science - Machine Learning
I.3.5
- Language
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.
Comment: Presented in SoCG'19 Young Researchers Forum (CG:YRF)