Triangulating simplicial point sets in space

ABSTRACT

A set P of points in Rd is called simplicial if it has dimension d and contains exactly d + 1 extreme points. We show that when P contains n interior points, there is always one point, called a splitter, that partitions P into d + 1 simplices, none of which contain more than dn /(d + 1) points. A splitter can be found in &Ogr; (d4n) time. Using this result, we give a &Ogr; (d4n log1+1/d n) algorithm for triangulating simplicial point sets that are in general position. In R3 we give an &Ogr; (n logn + k) algorithm for triangulating arbitrary point sets, where k is the number of simplices produced. We exhibit sets of 2n + 1 points in R3 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.

REFERENCES

• 1: B. Grt~nbaum, Convez Polytopes, Wiley, 1967.
• 2: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 3: B.L. Rothschild and E.G. Straus, "On Triangulations of the Convex Hull of n Points," Combinatorica, vol. 5, pp. 167- 179, 1985.
• 4: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 5: D. I(irkpatrick, "Optimal Search in Planar Subdivisions," SiAilg j. Computing, vol. 12, pp. 28-35, 1983.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification