Instituto de Computação - UNICAMP
Return to project main page
The second part is a sequence of n identifiers and points coordinates. Each vertex is indexed by a (increasing) integer, starting from zero, and is represented by its x and y coordinates each of which is written with six decimal places.
Finally, the third part is a list of (allowed) edges described by the its endpoints' indexes and its length. The length is presented rounded to six decimal places to avoid pitfalls and to facilitate comparisons. The list end is marked by the negative integer -1.
Any blank line or started by a '#' is considered as comments and is discarded. As an example, here is the representation of the vertices of a square with coordinates (10, 0) (0, 10) (-10, 0) and (0, -10):
There is a total of 210 MDTP instances, each one having between 10 and 70 points, all with the complete set of edges allowed:
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail:
MDTP - Minumum Dilation Triangulation Problem, by P. J. de Rezende, C. C. de Souza, A. F. Brandt and Miguel F. A. de M. Gaiowski
Citing this page:
-
Use the BibTeX entry:
@Misc{art-gallery-instances-page,
author = {Pedro J. de Rezende and Cid C. de Souza and Aléx. F. Brandt and Miguel F. A. de M. Gaiowski},
title = {The {Minimum Dilation Problem} Project},
year = {2014},
note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Dilation}}
}
File Format: Instances
Each file consists of three parts. The first part is an integer value n that represents the number of points.The second part is a sequence of n identifiers and points coordinates. Each vertex is indexed by a (increasing) integer, starting from zero, and is represented by its x and y coordinates each of which is written with six decimal places.
Finally, the third part is a list of (allowed) edges described by the its endpoints' indexes and its length. The length is presented rounded to six decimal places to avoid pitfalls and to facilitate comparisons. The list end is marked by the negative integer -1.
Any blank line or started by a '#' is considered as comments and is discarded. As an example, here is the representation of the vertices of a square with coordinates (10, 0) (0, 10) (-10, 0) and (0, -10):
| 4 | ||
| 0 | 10.000000 | 0.000000 |
| 1 | 0.000000 | 10.000000 |
| 2 | -10.000000 | 0.000000 |
| 3 | 0.000000 | -10.000000 |
| 0 | 1 | 14.142136 |
| 0 | 2 | 20.000000 |
| 0 | 3 | 14.142136 |
| 1 | 2 | 14.142136 |
| 1 | 3 | 20.000000 |
| 2 | 3 | 14.142136 |
| -1 |
Instances MDTP2014a
Instances and results presented in the paper Minimum Dilation Triangulation: Reaching Optimality Efficiently -- by Aléx F. Brandt, Miguel M. Gaiowski, Pedro de Rezende, and Cid de Souza.There is a total of 210 MDTP instances, each one having between 10 and 70 points, all with the complete set of edges allowed:
- uniform distribution - instances[.tar.gz] (1.4MB) - results[.tar.gz] (72KB)
References
- [1] Aléx Brandt, Miguel Gaiowski, Pedro de Rezende, and Cid de Souza. Minimum Dilation Triangulation: Reaching Optimality Efficiently , In Proc. of the 26th Canadian Conference on Computational Geometry (CCCG), 2014.
Address
Cid C. de Souza, and Pedro J. de RezendeUniversidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: