Smoothing imprecise 1-dimensional terrains

C.M. Gray, M. Löffler, R.I. Silveira

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic


We study optimization problems for polyhedral terrains in the presence of data imprecision. An imprecise terrain is given by a triangulated point set where the height component of the vertices is speci¯ed by an interval of possible values. We restrict ourselves to terrains with a one-dimensional projection, usually referred to as 1.5-dimensional terrains, where an imprecise terrain is given by an x-monotone polyline, and the y-coordinate of each vertex is not ¯xed but only constrained to a given interval. Motivated mainly by applications in terrain analysis, in this paper we study ¯ve di®erent optimization measures related to obtaining smooth terrains, for the 1.5-dimensional case. In particular, we present exact algorithms to minimize and maximize the average turning angle, as well as to minimize the maximum slope change. Furthermore, we also give approximation algorithms to minimize the largest turning angle and to maximize the smallest turning angle.
Originele taal-2Engels
TitelAbstracts 24th European Workshop on Computational Geometry (EuroCG'08, Nancy, France, March 18-20, 2008)
RedacteurenS. Petitjean
Plaats van productieVandoeuvre-lès-Nancy
StatusGepubliceerd - 2008


Duik in de onderzoeksthema's van 'Smoothing imprecise 1-dimensional terrains'. Samen vormen ze een unieke vingerafdruk.

Citeer dit