Large k-Gons in a 1.5D Terrain

0567939 - ÚI 2023 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Keikha, Vahideh
Large k-Gons in a 1.5D Terrain.
Computing and Combinatorics: 28th International Conference, COCOON 2022 Proceedings. Cham: Springer, 2022 - (Zhang, Y.; Miao, D.; Möhring, R.), s. 49-60. Lecture Notes in Computer Science, 13595. ISBN 978-3-031-22104-0. ISSN 0302-9743. E-ISSN 1611-3349.
[COCOON 2022: International Computing and Combinatorics Conference /28./. Shenzhen (CN), 22.10.2022-24.10.2022]
Grant CEP: GA ČR(CZ) GJ19-06792Y
Institucionální podpora: RVO:67985807
Klíčová slova: 1.5D terrain * Optimal area * Optimal perimeter * Approximation algorithm
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Given is a 1.5D terrain T, i.e., an x-monotone polygonal chain in R2. For a given 2 ≤ k≤ n, our objective is to approximate the largest area or perimeter convex object of exactly or at most k vertices inside T. For a constant k≥ 3, we design a near linear time FPTAS that approximates the largest convex polygons with at most k vertices, within a factor (1 - ϵ). For the case where k= 2, we discuss an O(n) time exact algorithm for computing the longest line segment in T, and for k= 3, we design an O(n2) time exact algorithm for computing the largest-perimeter triangle that lies within T.
Trvalý link: https://hdl.handle.net/11104/0339206