scientific article; zbMATH DE number 4064506

From MaRDI portal
Publication:3798256





[For the entire collection see Zbl 0643.00031.] An algorithm for constructing the greedy triangulation of any planar straight-line graph with n vertices in time \(O(n^ 2 \log n)\) and space O(n) is presented. The upper time-space bound implied by the algorithm in particular improves Gilbert's simultaneous \(O(n^ 2 \log n)\)-time and \(O(n^ 2)\)-space bound for finding the greedy triangulation of an n- point planar point set. A theorem suggesting a good expected time- performance of the presented algorithm is proved.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798256)