An Optimal Bound for Conforming Quality Triangulations
No Thumbnail Available
Date
1994-03-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper shows that for any plane geometric graph <I>G</I> with <I>n</I> vertices, there exists a triangulation <I>T</I> that conforms to <I>G</I>, i.e. each edge of <I>G</I> is the union of some edges of <I>T</I>, where <I>T</I> has O(<I>n^2)</I> vertices with each angle of its triangles measuring no more than <I>(11*pi)/15</I>. Additionally, <I>T</I> can be computed in O(<I>n^2log n)</I> time.