Triangulating point sets in space
Tóm tắt
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.
Tài liệu tham khảo
D. Avis and H. ElGindy, Triangulating simplicial point sets in space,Proceedings of the Second ACM Conference on Computational Geometry, IBM, Yorktown Heights, New York, 1986.
H. Edelsbrunner, F. P. Preparata, and D. B. West, Tetrahedrizing point sets in three dimensions, Report No. UIUC DCS-R-86-1310, Department of Computer Science, University of Illinois at Urbana-Champaign, 1986.
B. Grünbaum,Convex Polytopes, Wiley, New York, 1967.
D. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput. 12 (1983), 28–35.
F. P. Preparata and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions,Comm. ACM 22 (1977), 87–93.
F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985.