Smoothing imprecise 1.5D terrains

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

doi:10.1007/978-3-540-93980-1_17

Smoothing imprecise 1.5D terrains

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Approximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers)
Editors	E. Bampis, M. Skutella
Place of Publication	Berlin
Publisher	Springer
Pages	214-226
ISBN (Print)	978-3-540-93979-5
DOIs	https://doi.org/10.1007/978-3-540-93980-1_17
Publication status	Published - 2009

Publication series

Name	Lecture Notes in Computer Science
Volume	5426
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-540-93980-1_17

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). Springer. https://doi.org/10.1007/978-3-540-93980-1_17

@inproceedings{4ed9dfa21ef344898189744dd56ec1c8,

title = "Smoothing imprecise 1.5D terrains",

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.",

author = "C.M. Gray and M. L{\"o}ffler and R.I. Silveira",

year = "2009",

doi = "10.1007/978-3-540-93980-1_17",

language = "English",

isbn = "978-3-540-93979-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "214--226",

editor = "E. Bampis and M. Skutella",

booktitle = "Approximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers)",

}

Smoothing imprecise 1.5D terrains. / Gray, C.M.; Löffler, M.; Silveira, R.I.
Approximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers). ed. / E. Bampis; M. Skutella. Berlin: Springer, 2009. p. 214-226 (Lecture Notes in Computer Science; Vol. 5426).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Smoothing imprecise 1.5D terrains

AU - Gray, C.M.

AU - Löffler, M.

AU - Silveira, R.I.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-93980-1_17

DO - 10.1007/978-3-540-93980-1_17

M3 - Conference contribution

SN - 978-3-540-93979-5

T3 - Lecture Notes in Computer Science

SP - 214

EP - 226

BT - Approximation and Online Algorithms (6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers)

A2 - Bampis, E.

A2 - Skutella, M.

PB - Springer

CY - Berlin

ER -

Smoothing imprecise 1.5D terrains

Abstract

Publication series

Access to Document

Fingerprint

Cite this