## Abstract

Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T _{1} and T _{2} that share no diagonals, it is always possible to assign height values to the vertices of P such that P∪T _{1}∪T _{2} becomes a convex 3-polytope. Dekster found a counter example but left open the questions of deciding if a given configuration corresponds to a convex 3-polytope, and constructing such realizations when they exist. This paper presents a characterization of realizable configurations for Guibas' conjecture based on work from the area of polytope convexity testing. Our approach to the decision and construction problems is a reduction to a linear-inequality feasibility problem. The approach is also related to methods used for deciding if an arbitrary triangulation of a point set is a regular triangulation. We show two reductions, one based directly on a global convexity condition resulting in number of inequalities that is quadratic in the number of vertices of P, and one based on an equivalent local convexity condition resulting in a linear number of inequalities.

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

Pages (from-to) | 41-47 |

Number of pages | 7 |

Journal | Computational Geometry: Theory and Applications |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - May 2004 |

## Keywords

- Computational geometry
- Convex polytopes
- Convexity theory
- Graph drawing
- Linear programming
- Projections
- Realizations
- Triangulations

## ASJC Scopus subject areas

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