On the minimum number of simplex shapes in longest edge bisection refinement of a regular n-simplex

G. Aparicio, L.G. Casado, E.M.T. Hendrix, B.G. Toth, I. García

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex 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 sub-tree. Irregular sub-simplices 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 Branch-and-Bound (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 3-simplex. 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.
LanguageEnglish
Pages17-32
JournalInformatica
Volume26
Issue number1
DOIs
Publication statusPublished - 2015

Fingerprint

Bisection
Refinement
Branch and bound method
Binary trees
Global optimization
Binary Search Tree
Branch and Bound Method
Costs
Binary Tree
Branch-and-bound
Combinatorial Problems
Global Optimization
Higher Dimensions
Workload
Optimization Methods
Computational Cost
Irregular
High Performance
Choose
Unit

Cite this

Aparicio, G. ; Casado, L.G. ; Hendrix, E.M.T. ; Toth, B.G. ; García, I. / On the minimum number of simplex shapes in longest edge bisection refinement of a regular n-simplex. In: Informatica. 2015 ; Vol. 26, No. 1. pp. 17-32.
@article{693416d277e445a3b301f0667b4c6305,
title = "On the minimum number of simplex shapes in longest edge bisection refinement of a regular n-simplex",
abstract = "In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex 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 sub-tree. Irregular sub-simplices 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 Branch-and-Bound (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 3-simplex. 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.",
author = "G. Aparicio and L.G. Casado and E.M.T. Hendrix and B.G. Toth and I. Garc{\'i}a",
year = "2015",
doi = "10.15388/Informatica.2015.36",
language = "English",
volume = "26",
pages = "17--32",
journal = "Informatica",
issn = "0868-4952",
publisher = "IOS Press",
number = "1",

}

On the minimum number of simplex shapes in longest edge bisection refinement of a regular n-simplex. / Aparicio, G.; Casado, L.G.; Hendrix, E.M.T.; Toth, B.G.; García, I.

In: Informatica, Vol. 26, No. 1, 2015, p. 17-32.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On the minimum number of simplex shapes in longest edge bisection refinement of a regular n-simplex

AU - Aparicio, G.

AU - Casado, L.G.

AU - Hendrix, E.M.T.

AU - Toth, B.G.

AU - García, I.

PY - 2015

Y1 - 2015

N2 - In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex 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 sub-tree. Irregular sub-simplices 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 Branch-and-Bound (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 3-simplex. 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.

AB - In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex 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 sub-tree. Irregular sub-simplices 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 Branch-and-Bound (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 3-simplex. 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.

U2 - 10.15388/Informatica.2015.36

DO - 10.15388/Informatica.2015.36

M3 - Article

VL - 26

SP - 17

EP - 32

JO - Informatica

T2 - Informatica

JF - Informatica

SN - 0868-4952

IS - 1

ER -