EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Optimal Translation Covers for Colored Line Segments

Heeyeon Kim, Sang Won Bae, Sang Duk Yoon

Symmetry · 15.08.2026 · 18 (8) · 1377

DOI: 10.3390/sym18081377 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Symmetry, online erschienen am 15.08.2026. Verfasst von Heeyeon Kim und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a variant of the translation cover problem for colored line segments in the plane. For each color i∈{1,…,k}, we are given a set Si of n line segments, and the goal is to choose one segment from each color class so that the selected segments have the smallest possible translation cover area. Equivalently, the selected segments may be translated independently, and we minimize the area of the convex hull of their translated copies. We give algorithms for every fixed number k>1 of colors. For k=2, we obtain an O(nlogn)-time algorithm using O(n) space. For k=3, we obtain a deterministic O(n2logn)-time algorithm and a randomized algorithm with expected O(n2) running time; both use O(n) space. For k=4, we obtain an O(n4)-time algorithm using O(n) space. For every fixed k>4, we obtain an O(n4logn)-time algorithm using O(n2polylogn) space, thereby avoiding the enumeration of all nk colorful selections.

Zitieren

APA

Kim, H., Bae, S. W., & Yoon, S. D. (2026). Optimal Translation Covers for Colored Line Segments. Symmetry, 18(8), 1377. https://doi.org/10.3390/sym18081377

Vancouver

Kim H, Bae SW, Yoon SD. Optimal Translation Covers for Colored Line Segments. Symmetry. 2026;18(8):1377. doi:10.3390/sym18081377

BibTeX
@article{Kim2026,
  author = {Kim, Heeyeon and Bae, Sang Won and Yoon, Sang Duk},
  title = {Optimal Translation Covers for Colored Line Segments},
  journal = {Symmetry},
  year = {2026},
  volume = {18},
  number = {8},
  pages = {1377},
  doi = {10.3390/sym18081377}
}
Kostenlos starten →