Optimal Translation Covers for Colored Line Segments
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).
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}
}
EUVIMED