On Computing and Drawing Maxmin-Height Covering Triangulation

Zhu, Binhai and Deng, Xiaotie (1998) On Computing and Drawing Maxmin-Height Covering Triangulation. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 464-466 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_48).

Full text not available from this repository.


Given a simple polygon P, a covering triangulation is another triangulation over the vertices of P and some inner Steiner points (see Fig 1 for a covering triangulation generated by our heuristic). In other words, when computing a covering triangulation one is only allowed to add Steiner points in the interior of P. This problem is originally from mesh smoothing: one is not happy with the mesh over a specific region (say P) and would like to re-triangulate that region. Certainly, adding Steiner points on the boundary of P would destroy the neighboring part of P and would result in further changes of the mesh.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_48
Classifications:Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others
ID Code:395

Repository Staff Only: item control page


M. Bern, D. Dobkin, and D. Eppstein. Triangulating polygons without large angles. Intl. J. Comput. Geom. Th. and Appl., 5:171-192, 1995.

S. Mitchell. Finding a covering triangulation whose maximum angle is provably small. Proc. 17th Australian Computer Science Conference, pages 55-64, 1994.

S. Mitchell. Approximating the maxmin-angle covering triangulation. Comput. Geom. Theo. and Appl., 7:93-111, 1997.

H. ElGindy, H. Everett and G.T. Toussaint. Slicing an ear in linear time. Patt. Recog. Lett., 14:719-722, 1993.