Computing Balanced Convex Partitions of Lines

被引：0
作者：
Sergey Bereg
机构：
[1] University of Texas at Dallas,Department of Computer Science
来源：
Algorithmica | 2023年 / 85卷
关键词：
Computational geometry; Ham-sandwich cut; Balanced partitions;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Dujmović and Langerman (Discrete Comput Geom 49(1):74–88, 2013) proved a ham-sandwich cut theorem for an arrangement of lines in the plane. Recently, Xue and Soberón (Discrete Comput Geom 66:1150–1167, 2021) generalized it to balanced convex partitions of lines in the plane. In this paper, we study the computational problems of computing a ham-sandwich cut balanced convex partitions for an arrangement of lines in the plane. We show that both problems can be solved in polynomial time.
引用
收藏
页码：2515 / 2528
页数：13
相关论文
共 32 条
  • [1] Bereg S(2009)Orthogonal equipartitions Comput. Geom. Theory Appl. 42 305-314
  • [2] Bespamyatnikh S(2000)Generalizing ham sandwich cuts to equitable subdivisions Discrete Comput. Geom. 24 605-622
  • [3] Kirkpatrick D(1998)Optimal slope selection via cuttings Comput. Geom. Theory Appl. 10 23-29
  • [4] Snoeyink J(1989)An optimal-time algorithm for slope selection SIAM J. Comput. 18 792-810
  • [5] Brönnimann H(1992)A randomized algorithm for slope selection Intern. J. Comput. Geom. Appl. 2 1-27
  • [6] Chazelle B(2013)A center transversal theorem for hyperplanes and applications to graph drawing Discrete Comput. Geom. 49 74-88
  • [7] Cole R(1990)Computing median-of-squares regression lines and guided topological sweep J. Am. Stat. Assoc. 85 115-119
  • [8] Salowe J(1975)On computing the length of longest increasing subsequences Discrete Math. 11 29-35
  • [9] Steiger W(2021)Discrete geometry on colored point sets in the plane—a survey Graphs Comb. 37 1-53
  • [10] Szemerédi E(1993)Optimal slope selection via expanders Inform. Process. Lett. 47 115-122
1234