Ponencia
A simple and less slow method for counting triangulations and for related problems
Autor/es | Ray, Saurabh
Seidel, Raimund |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-06 |
Publicado en |
|
Resumen | 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 ... 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. |
Cita | Ray, S. y Seidel, R. (2004). A simple and less slow method for counting triangulations and for related problems. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A simple and less slow method ... | 187.3Kb | [PDF] | Ver/ | |