## Abstract

In 1994 Grünbaum showed that, given a point set S in R ^{3}, it is always possible to construct a polyhedron whose vertices are exactly S. Such a polyhedron is called a polyhedronization of S. Agarwal et al. extended this work in 2008 by showing that there always exists a polyhedronization that can be decomposed into a union of tetrahedra (tetrahedralizable). In the same work they introduced the notion of a serpentine polyhedronization for which the dual of its tetrahedralization is a chain. In this work we present a randomized algorithm running in O(n ^{log6}n) expected time which constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.

Original language | English (US) |
---|---|

Pages (from-to) | 148-153 |

Number of pages | 6 |

Journal | Computational Geometry: Theory and Applications |

Volume | 46 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2013 |

## Keywords

- Convex hull
- Gift wrapping
- Serpentine
- Tetrahedralization

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics