Back to Search Start Over

Few Cuts Meet Many Point Sets.

Authors :
Har-Peled, Sariel
Jones, Mitchell
Source :
Algorithmica. Apr2023, Vol. 85 Issue 4, p965-975. 11p.
Publication Year :
2023

Abstract

We study the problem of how to split many point sets in R d into smaller parts using a few (shared) splitting hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*HYPERPLANES
*POINT set theory
*APPROXIMATION algorithms
*GREEDY algorithms

Details

Language :
English
ISSN :
01784617
Volume :
85
Issue :
4
Database :
Academic Search Index
Journal :
Algorithmica
Publication Type :
Academic Journal
Accession number :
162755637
Full Text :
https://doi.org/10.1007/s00453-022-01059-y
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details