On realistic terrains
type: Item
instance of: scholarly article
title: On realistic terrains
zbMATH Open document ID: 1152.65034
author: Esther Moet
author: A. Frank van der Stappen
author: Marc Van Kreveld
published in: Computational Geometry
publication date: 2008-07-29T00:00:00Z
review text: This paper is focused on the worst-case complexities of the visibility map and the shortest paths on realistic polyhedral terrains. The authors give a set of input assumptions which can reasonably present the values of the model parameters in terrains that arise in practice. The minimal value of the angle in any triangle, edge length ratio and low-density triangulation are taken into the consideration in these assumptions. The authors show that only the given assumptions together (not separately) can achieve a subquadratic upper bound on the complexity for the visibility map of a terrain for both parallel and perspective views. Furthermore, an additional assumption is introduced for distance structures, bisectors, shortest path maps and Voronoi diagrams on terrains and the upper and lower bounds on their complexities is proved. The fourth input assumption relates to the steepness of the terrain.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5304596
zbMATH Keywords: polyhedral terrain
zbMATH Keywords: visibility map
zbMATH Keywords: shortest path
zbMATH Keywords: triangulation
zbMATH Keywords: Voronoi diagram
zbMATH Keywords: geodesic region
MaRDI profile type: Publication
full work available at URL: j.comgeo.2007.10.008
OpenAlex ID: W2202869537
cites work: Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
cites work: On the union of κ-round objects
cites work: Nonoverlap of the star unfolding
cites work: SHORTEST PATHS ON A POLYHEDRON, Part I: COMPUTING SHORTEST PATHS
cites work: Linear size binary space partitions for uncluttered scenes
cites work: Vertical ray shooting for fat objects
cites work: Models and motion planning
cites work: Realistic input models for geometric algorithms
cites work: The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
cites work: Local polyhedra and geometric graphs
cites work: Efficient computation of geodesic shortest paths
cites work: Efficient hidden surface removal for objects with small union size
cites work: Fat Triangles Determine Linearly Many Holes
cites work: The Discrete Geodesic Problem
cites work: Q3601537
cites work: Range Searching and Point Location among Fat Objects
cites work: Range searching in low-density environments
cites work: Algorithms and Data Structures
cites work: Smoothed analysis of algorithms
cites work: Motion planning in environments with low obstacle density
cites work: The complexity of the free space for motion planning amidst fat obstacles
cites work: On fat partitioning, fat covering and the union size of polygons
DOI: 10.1016/J.COMGEO.2007.10.008
description: scientific article; zbMATH DE number 5304596