New Results for the Minimum Weight Triangulation Problem

Simple item page
dc.contributor.authorHeath, Lenwood S.en
dc.contributor.authorPemmaraju, Sriram V.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:17Zen
dc.date.available2013-06-19T14:36:17Zen
dc.date.issued1992en
dc.description.abstractThe current best polynomial time approximation algorithm produces a triangulation that can be O(log n) times the weight of the optimal triangulation. We propose an algorithm that triangulates a set P of n points in a plane in O(n3) time and that never does worse than the greedy triangulation. We investigate issues of local optimality pertaining to known triangulation algorithms and suggest an interesting new approach to studying triangulation algorithms. We restate the minimum weight triangulation problem as a graph problem and show the NP-hardness of a closely related graph problem. Finally, we show that the constrained problem of computing the minimum weight triangulation, given a set of points in a plane and enough edges to form a triangulation, is NP-hard. These results are an advance towards a proof that the minimum weight triangulation problem is NP-hard.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000310/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000310/01/TR-92-30.pdfen
dc.identifier.trnumberTR-92-30en
dc.identifier.urihttp://hdl.handle.net/10919/19756en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleNew Results for the Minimum Weight Triangulation Problemen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-92-30.pdf
Size:
1.65 MB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports