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.

 Please e-mail replies to sen@research.att.com

    Thanks in advance,

                    - Sandeep Sen