```From:           pankaj@cs.duke.edu (Pankaj Kumar Agarwal)
Newsgroups:     sci.math
Subject:        Triangulating convex polytopes
Date:           12 Oct 90 15:07:02 GMT
Organization:   Duke University Computer Science Dept.; Durham, N.C.
```

```I am posting this message on behalf of
a friend of mine. Please send all
replies to the address given below.
---------------------------------------------

Given a convex polytope in d dimensions, I would like to
triangulate it (into d-simplices) which has one
of the following two properties

1.  Any line (1-face) intersects at most \$O(\log N)\$
simplices (if the polytope has N vertices)

or

2. Every vertex is incident on a number of simplices
which does not depend on N (can depend on d).

In 2 dimensions there are triangulation schemes where
properties 2 or 3 can be satisfied. In 3-D property 2
can be satisfied but I could not come up with a scheme
to satisfy property 3. For d > 3, I could not come up
with anything. I am not even sure if such decomposition
is possible in higher dimensions or how close can one
get to the above conditions. More specifically, I would
be resaonably happy to know about triangulation schemes
for which the bounds in (2) or (3) are \$O(\log^{d} N)\$.

I will be very grateful if someone can provide me with
some useful pointers (of course an answer is always
welcome). The motivation behind this query is algorithmic
application.