Few Cuts Meet Many Point Sets

Sariel Har-Peled; Mitchell Jones

doi:10.1007/s00453-022-01059-y

Few Cuts Meet Many Point Sets

Sariel Har-Peled, Mitchell Jones

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	965-975
Number of pages	11
Journal	Algorithmica
Volume	85
Issue number	4
DOIs	https://doi.org/10.1007/s00453-022-01059-y
State	Published - Apr 2023

Keywords

Approximation algorithms
Ham-Sandwich Theorem
Submodular optimization

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-022-01059-y

Library availability

Discover UIUC Full Text

Cite this

@article{47725eb2c3a342fba18a8fbb1382f383,

title = "Few Cuts Meet Many Point Sets",

abstract = "We study the problem of how to split many point sets in Rd 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.",

keywords = "Approximation algorithms, Ham-Sandwich Theorem, Submodular optimization",

author = "Sariel Har-Peled and Mitchell Jones",

note = "Funding Information: Sariel Har-Peled was partially supported by NSF AF awards CCF-1421231, CCF-1217462, and CCF-1907400. Mitchell Jones was partially supported by NSF AF awards CCF-1421231 and CCF-1907400. The authors also thank the anonymous referees for their detailed and useful feedback. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = apr,

doi = "10.1007/s00453-022-01059-y",

language = "English (US)",

volume = "85",

pages = "965--975",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Few Cuts Meet Many Point Sets

AU - Har-Peled, Sariel

AU - Jones, Mitchell

N1 - Funding Information: Sariel Har-Peled was partially supported by NSF AF awards CCF-1421231, CCF-1217462, and CCF-1907400. Mitchell Jones was partially supported by NSF AF awards CCF-1421231 and CCF-1907400. The authors also thank the anonymous referees for their detailed and useful feedback. Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/4

Y1 - 2023/4

N2 - We study the problem of how to split many point sets in Rd 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.

AB - We study the problem of how to split many point sets in Rd 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.

KW - Approximation algorithms

KW - Ham-Sandwich Theorem

KW - Submodular optimization

UR - http://www.scopus.com/inward/record.url?scp=85141973203&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85141973203&partnerID=8YFLogxK

U2 - 10.1007/s00453-022-01059-y

DO - 10.1007/s00453-022-01059-y

M3 - Article

AN - SCOPUS:85141973203

SN - 0178-4617

VL - 85

SP - 965

EP - 975

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

Few Cuts Meet Many Point Sets

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this