Storing the subdivision of a polyhedral surface
type: Item
instance of: scholarly article
title: Storing the subdivision of a polyhedral surface
zbMATH Open document ID: 0615.52008
DOI: 10.1007/BF02187877
author: David M. Mount
published in: Discrete \& Computational Geometry
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131016
review text: Let P be a polyhedron, composed of a finite number of vertices, n (say) edges, and convex polygonal faces in 3-space, and suppose P simply- connected (although this condition can be relaxed a little). Let P be subdivided by a graph Q consisting of a finite number m (say) of geodesics on P, and suppose that there are K intersections between edges of P and geodesics of Q. The author constructs an algorithm which represents the subdivision in space \(O((n+m)\log (n+m)),\) and can be built in time \(O(K+(n+m)\log (n+m)).\) This enables various queries about the subdivision (for example, to which region a given point belongs) to be answered efficiently.
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 51M20
zbMATH DE Number: 3996524
zbMATH Keywords: geodesic
zbMATH Keywords: incidence structure
zbMATH Keywords: query processing
zbMATH Keywords: polyhedral surface
zbMATH Keywords: algorithm
zbMATH Keywords: subdivision
MaRDI profile type: Publication
cites work: A linear 5-coloring algorithm of planar graphs
cites work: Fast detection of polyhedral intersection
cites work: Efficient uses of the past
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Computing convolutions by reciprocal search
cites work: Primitives for the manipulation of general subdivisions and the computation of Voronoi
cites work: Optimal Search in Planar Subdivisions
cites work: Location of a Point in a Planar Subdivision and Its Applications
cites work: The Discrete Geodesic Problem
cites work: Finding the intersection of two convex polyhedra
cites work: A New Approach to Planar Point Location
cites work: Intersection and Closest-Pair Problems for a Set of Planar Discs
cites work: On Shortest Paths in Polyhedral Spaces
description: scientific article; zbMATH DE number 3996524