Repositorio de producción científica de la Universidad de Sevilla

A simple and less slow method for counting triangulations and for related problems

 

Advanced Search
 
Opened Access A simple and less slow method for counting triangulations and for related problems
Cites
Show item statistics
Icon
Export to
Author: Ray, Saurabh
Seidel, Raimund
Date: 2004
Document type: Presentation
Abstract: We present a simple dynamic programming based method for counting straight-edge triangulations of planar point sets. This method can be adapted to solve related problems such as nding the best triangulation of a point set according to certain optimality criteria, or generating a triangulation of a point set uniformly at random. We have implemented our counting method. It appears to be substantially less slow than previous methods: instances with 20 points, which used to take minutes, can now be handled in less than a second, and instances with 30 points, which used to be solvable only by employing several workstations in parallel over a substantial amount of time, an now be solved in about one minute on a single standard workstation.
Size: 187.3Kb
Format: PDF

URI: http://hdl.handle.net/11441/55368

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)