Number of the records: 1  

Large k-Gons in a 1.5D Terrain

  1. 1.
    0567939 - ÚI 2023 RIV CH eng C - Conference Paper (international conference)
    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]
    R&D Projects: GA ČR(CZ) GJ19-06792Y
    Institutional support: RVO:67985807
    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)

    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.
    Permanent Link: https://hdl.handle.net/11104/0339206

     
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.