Original title: Large Perimeter Objects Surrounded by a 1.5D Terrain
Authors: Keikha, Vahideh
Document type: Research reports
Year: 2022
Language: eng
Series: Technical Report, volume: V-1286
Abstract: Given is a 1.5D terrain T , i.e., an x-monotone polygonal chain in R2. Our objective is to approximate the largest area or perimeter convex polygon with at most k vertices inside T . For a constant k > 0, we design an FPTAS that efficiently approximates such polygons within a factor (1 − ǫ). For the special case of the´largest-perimeter contained triangle in T , we design an O(n log n) time exact algorithm that matches the same result for the area measure.

Institution: Institute of Computer Science AS ČR (web)
Document availability information: Fulltext is available in the digital repository of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0330996

Permalink: http://www.nusl.cz/ntk/nusl-508571


The record appears in these collections:
Research > Institutes ASCR > Institute of Computer Science
Reports > Research reports