Smoothing imprecise 1.5D terrains

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

We study optimization problems in an imprecision model for polyhedral terrains. An imprecise terrain is given by a triangulated point set where the height component of the vertices is specified by an interval of possible values. We restrict ourselves to 1.5-dimensional terrains: an imprecise terrain is given by an x-monotone polyline, and the y-coordinate of each vertex is not fixed but constrained to a given interval. Motivated by applications in terrain analysis, in this paper we present two linear-time approximation algorithms, for minimizing the largest turning angle and for maximizing the smallest one. In addition, we also provide linear time exact algorithms for minimizing and maximizing the sum of the turning angles.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers)
EditorsE. Bampis, M. Skutella
Place of PublicationBerlin
PublisherSpringer
Pages214-226
ISBN (Print)978-3-540-93979-5
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5426
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Smoothing imprecise 1.5D terrains'. Together they form a unique fingerprint.

  • Cite this

    Gray, C. M., Löffler, M., & Silveira, R. I. (2009). Smoothing imprecise 1.5D terrains. In E. Bampis, & M. Skutella (Eds.), Approximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers) (pp. 214-226). (Lecture Notes in Computer Science; Vol. 5426). Berlin: Springer. https://doi.org/10.1007/978-3-540-93980-1_17