Few Cuts Meet Many Point Sets

Matousek, J., Patáková, Z.: Multilevel polynomial partitions and simplified range searching. Disc. Comput. Geom. 54(1), 22–41 (2015). https://doi.org/10.1007/s00454-015-9701-2

Agarwal, P.K., Aronov, B., Ezra, E., Zahl, J.: Efficient algorithm for generalized polynomial partitioning and its applications. SIAM J. Comput. 50(2), 760–787 (2021). https://doi.org/10.1137/19M1268550

Sheffer, A.: Polynomial Methods and Incidence Theory. Cambridge University Press, Cambridge (2022). https://doi.org/10.1017/9781108959988

Stone, A.H., Tukey, J.W.: Generalized “sandwich’’ theorems. Duke Math. J. 9(2), 356–359 (1942). https://doi.org/10.1215/S0012-7094-42-00925-6

Har-Peled, S., Jones, M.: On separating points by lines. Disc. Comput. Geom. 63(3), 705–730 (2020). https://doi.org/10.1007/s00454-019-00103-z

Lo, C.-Y., Matoušek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Disc. Comput. Geom. 11, 433–452 (1994). https://doi.org/10.1007/BF02574017

Bárány, I., Hubard, A., Jerónimo, J.: Slicing convex sets and measures by a hyperplane. Disc. Comput. Geom. 39(1–3), 67–75 (2008). https://doi.org/10.1007/s00454-007-9021-2

Blagojević, P.V., Soberón, P.: Thieves can make sandwiches. Bull. Lond. Math. Soc. 50(1), 108–123 (2018). https://doi.org/10.1112/blms.12109

Ramos, E.A.: Equipartition of mass distributions by hyperplanes. Disc. Comput. Geom. 15(2), 147–167 (1996). https://doi.org/10.1007/BF02717729

Schnider, P.: Ham-sandwich cuts and center transversals in subspaces. In: Proc. 35th Int. Annu. Sympos. Comput. Geom. (SoCG). LIPIcs, vol. 129, pp. 56– 15615 ( 2019). https://doi.org/10.4230/LIPIcs.SoCG.2019.56

Steiger, W., Zhao, J.: Generalized ham-sandwich cuts. Disc. Comput. Geom. 44(3), 535–545 (2010). https://doi.org/10.1007/s00454-009-9225-8

Kaplan, H., Matoušek, J., Sharir, M.: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique. Disc. Comput. Geom. 48(3), 499–517 (2012). https://doi.org/10.1007/s00454-012-9443-3

Agarwal, P.K., Matoušek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039–2062 (2013). https://doi.org/10.1137/120890855

Matoušek, J.: Geometric range searching. ACM Comput. Surv. 26(4), 421–461 (1994). https://doi.org/10.1145/197405.197408

Inamdar, T., Varadarajan, K.R.: On partial covering for geometric set systems. In: Speckmann, B., Tóth, C.D. (eds.) Proc. 34th Int. Annu. Sympos. Comput. Geom. (SoCG). LIPIcs, vol. 99, pp. 47– 14714. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern, Germany ( 2018). https://doi.org/10.4230/LIPIcs.SoCG.2018.47

Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982). https://doi.org/10.1007/BF02579435

Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71(4), 495–505 (2005). https://doi.org/10.1016/j.jcss.2005.05.002