Název: Large Perimeter Objects Surrounded by a 1.5D Terrain
Autoři: Keikha, Vahideh
Typ dokumentu: Výzkumné zprávy
Rok: 2022
Jazyk: eng
Edice: Technical Report, svazek: V-1286
Abstrakt: 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.

Instituce: Ústav informatiky AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v repozitáři Akademie věd.
Původní záznam: http://hdl.handle.net/11104/0330996

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-508571


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Ústav informatiky
Zprávy > Výzkumné zprávy