From:pankaj@cs.duke.edu (Pankaj Kumar Agarwal)Newsgroups:sci.mathSubject:Triangulating convex polytopesDate:12 Oct 90 15:07:02 GMTOrganization: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