INFORMATICA
International Journal


INFORMATICA, , Vol. 26, No. 1, 1732
© Institute of Mathematics and Informatics,
DOI: http://dx.doi.org/10.15388/Informatica.2015.36
ISSN 08684952
On the Minimum Number of Simplex Shapes in Longest Edge Bisection Refinement of a Regular nSimplex
Guillermo APARICIO, Leocadio G. CASADO^{1}, Eligius M.T. HENDRIX, Boglárka G.TÓTH, Inmaculada GARCIA
Research Group TIC146: High Performance Computing  Algorithms University of Almería, Spain Informatics Department, University of Almería (ceiA3), Spain Department of Computer Architecture, Universidad de Málaga, Spain Department of Differential Equations, Budapest University of Technology and Economics Hungary Email: guillermoaparicio@ual.es, leo@ual.es, eligius@uma.es, igarciaf@uma.es, bog@math.bme.hu
Abstract
In several areas like Global Optimization using branchandbound methods, the unit nsimplex is refined by bisecting the longest edge such that a binary search tree appears. This process generates simplices belonging to different shape classes. Having less simplex shapes facilitates the prediction of the further workload from a node in the binary tree, because the same shape leads to the same subtree. Irregular subsimplices generated in the refinement process may have more than one longest edge when n\geqslant 3. The question is how to choose the longest edge to be bisected such that the number of shape classes is as small as possible. We develop a BranchandBound (B&B) algorithm to find the minimum number of classes in the refinement process. The developed B&B algorithm provides a minimum number of eight classes for a regular 3simplex. Due to the high computational cost of solving this combinatorial problem, future research focuses on using high performance computing to derive the minimum number of shapes in higher dimensions.
Keywords:
regular simplex, longest edge bisection, branchandbound, combinatorial optimization, simplex shape
^{1}Corresponding author.
To preview Lithuanian abstract see full article
text
To preview full
article text in PDF format click here
You could obtain free Acrobat Reader from
Adobe
