DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.22

Minimum Partition of Polygons Under Width and Cut Constraints

Authors: Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

We study the problem of partitioning a polygon into the minimum number of subpolygons using cuts in predetermined directions such that each resulting subpolygon satisfies a given width constraint. A polygon satisfies the unit-width constraint for a set of unit vectors if the length of the orthogonal projection of the polygon on a line parallel to a vector in the set is at most one. We analyze structural properties of the minimum partition numbers, focusing on monotonicity under polygon containment. We show that the minimum partition number of a simple polygon is at least that of any subpolygon, provided that the subpolygon satisfies a certain orientation-wise convexity with respect to the polygon. As a consequence, we prove a partition analogue of the Bang’s conjecture about coverings of convex regions in the plane: for any partition of a convex body in the plane, the sum of relative widths of all parts is at least one. For any convex polygon, there exists a direction along which an optimal partition is achieved by parallel cuts. Given such a direction, an optimal partition can be computed in linear time.

Cite as

Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn. Minimum Partition of Polygons Under Width and Cut Constraints. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ISAAC.2025.22,
  author =	{Chung, Jaehoon and Iwama, Kazuo and Liao, Chung-Shou and Ahn, Hee-Kap},
  title =	{{Minimum Partition of Polygons Under Width and Cut Constraints}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.22},
  URN =		{urn:nbn:de:0030-drops-249302},
  doi =		{10.4230/LIPIcs.ISAAC.2025.22},
  annote =	{Keywords: Polygon partitioning, Width constraints, Plank problem}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.13

Inscribing or Circumscribing a Histogon to a Convex Polygon

Authors: Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract

We consider two optimization problems of approximating a convex polygon, one by a largest inscribed histogon and the other by a smallest circumscribed histogon. An axis-aligned histogon is an axis-aligned rectilinear polygon such that every horizontal edge has an integer length. A histogon of orientation θ is a copy of an axis-aligned histogon rotated by θ in counterclockwise direction. The goal is to find a largest inscribed histogon and a smallest circumscribed histogon over all orientations in [0,π). Depending on whether the horizontal width of a histogon is predetermined or not, we consider several different versions of the problem and present exact algorithms. These optimization problems belong to shape analysis, classification, and simplification, and they have applications in various cost-optimization problems.

Cite as

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn. Inscribing or Circumscribing a Histogon to a Convex Polygon. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.FSTTCS.2022.13,
  author =	{Chung, Jaehoon and Bae, Sang Won and Shin, Chan-Su and Yoon, Sang Duk and Ahn, Hee-Kap},
  title =	{{Inscribing or Circumscribing a Histogon to a Convex Polygon}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.13},
  URN =		{urn:nbn:de:0030-drops-174054},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.13},
  annote =	{Keywords: Shape simplification, Shape analysis, Histogon, Convex polygon}
}

Search Results

Documents authored by Chung, Jaehoon

Minimum Partition of Polygons Under Width and Cut Constraints

Abstract

Cite as

Inscribing or Circumscribing a Histogon to a Convex Polygon

Abstract

Cite as

Thanks for your feedback!

Could not send message