Triangulating point sets in space
type: Item
instance of: scholarly article
title: Triangulating point sets in space
zbMATH Open document ID: 0615.52007
DOI: 10.1007/BF02187874
author: Hossam ElGindy
author: David Avis
published in: Discrete \& Computational Geometry
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131013
review text: Let P be a set of n points in \(R^ d\), whose convex hull is a d-simplex. If there are n' interior points, the authors give an algorithm for finding a splitter, which is one of these points which splits conv P into \(d+1\) simplices, none of which contains more than \(dn'/(d+1)\) points, in time \(O(d^ 4+nd^ 2)\). Using this result, they can triangulate a set of n points in general position in \(R^ d\) in time \(O(nd^ 4\log_{1+1/d}n)\). There is an improved algorithm in \(R^ 3\).
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 51M20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3996523
zbMATH Keywords: simplicial point set
zbMATH Keywords: triangulation
zbMATH Keywords: algorithm
zbMATH Keywords: splitter
MaRDI profile type: Publication
cites work: Tetrahedrizing point sets in three dimensions
cites work: Q5547252
cites work: Optimal Search in Planar Subdivisions
cites work: Convex hulls of finite sets of points in two and three dimensions
cites work: Q3992847
description: scientific article; zbMATH DE number 3996523