Triangulating point sets in space |
| |
Authors: | David Avis Hossam ElGindy |
| |
Institution: | (1) School of Computer Science, McGill University, 805 Sherbrooke St. W., H3A 2K6 Montreal, Canada;(2) Department of Computer and Information Science, University of Pennsylvania, 19104 Philadelphia, PA, USA |
| |
Abstract: | A setP ofn points inR
d
is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn /(d + 1) points. A splitter can be found inO(d
4 +nd
2) time. Using this result, we give anO(nd
4 log1+1/d
n) algorithm for triangulating simplicial point sets that are in general position. InR
3 we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR
3 for which the number of simplices produced may vary between (n – 1)2 + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|