Number of the records: 1
Large k-Gons in a 1.5D Terrain
- 1.
SYSNO ASEP 0567939 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Large k-Gons in a 1.5D Terrain Author(s) Keikha, Vahideh (UIVT-O) ORCID, RID, SAI Source Title Computing and Combinatorics: 28th International Conference, COCOON 2022 Proceedings. - Cham : Springer, 2022 / Zhang Y. ; Miao D. ; Möhring R. - ISSN 0302-9743 - ISBN 978-3-031-22104-0 Pages s. 49-60 Number of pages 12 s. Publication form Print - P Action COCOON 2022: International Computing and Combinatorics Conference /28./ Event date 22.10.2022 - 24.10.2022 VEvent location Shenzhen Country CN - China Event type WRD Language eng - English Country CH - Switzerland Keywords 1.5D terrain ; Optimal area ; Optimal perimeter ; Approximation algorithm OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) R&D Projects GJ19-06792Y GA ČR - Czech Science Foundation (CSF) Institutional support UIVT-O - RVO:67985807 UT WOS 000916958900005 EID SCOPUS 85147986030 DOI 10.1007/978-3-031-22105-7_5 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2023
Number of the records: 1