Halving by a Thousand Cuts or Punctures

Sariel Har-Peled, Da Wei Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

For point sets P1, ..., Pk, a set of lines L is halving if any face of the arrangement A(L) contains at most |Pi|/2 points of Pi, for all i. We study the problem of computing a halving set of lines of minimal size. Surprisingly, we show a polynomial time algorithm that outputs a halving set of size O(o3/2), where o is the size of the optimal solution - this is of interest when o = o(log2 n). Our solution relies on solving a new variant of the weak ε-net problem for corridors, which we believe to be of independent interest. We also study other variants of this problem, including an alternative “dual” settings, where one needs to introduce a set of guards (i.e., points), such that no convex set avoiding the guards contains more than half the points of each point set.

Original languageEnglish (US)
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery
Pages1385-1397
Number of pages13
ISBN (Electronic)9781611977554
StatePublished - 2023
Externally publishedYes
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: Jan 22 2023Jan 25 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period1/22/231/25/23

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Halving by a Thousand Cuts or Punctures'. Together they form a unique fingerprint.

Cite this