Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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. The refinement usually selects the first longest edge and ends when the size of the sub-simplices generated in the refinement is smaller than a given accuracy. Irregular sub-simplices may have more than one longest edge only for n¿=¿3. The question is how to choose the longest edge to be bisected such that the number of sub-simplices in the generated binary tree is minimal. The difficulty of this Combinatorial Optimization problem increases with n. Therefore, heuristics are studied that aim to minimize the number of generated simplices
LanguageEnglish
Title of host publicationProceedings of the Computational Science and its Applications - ICCSA 2014, Part II
Place of PublicationCham
Pages115-125
DOIs
Publication statusPublished - 2014
Event14th ICCSA 2014, Guimarães, Portugal -
Duration: 30 Jun 20143 Jul 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8580
ISSN (Print)0302-9743

Conference

Conference14th ICCSA 2014, Guimarães, Portugal
Period30/06/143/07/14

Fingerprint

Bisection
Refinement
Heuristics
Binary Search Tree
Branch and Bound Method
Binary Tree
Combinatorial Optimization Problem
Global Optimization
Optimization Methods
Irregular
Choose
Minimise
Unit

Cite this

Aparicio, G., Casado, L. G., Tóth, B. G., Hendrix, E. M. T., & García, I. (2014). Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex. In Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II (pp. 115-125). (Lecture Notes in Computer Science; Vol. 8580). Cham. https://doi.org/10.1007/978-3-319-09129-7_9
Aparicio, G. ; Casado, L.G. ; Tóth, B.G. ; Hendrix, E.M.T. ; García, I. / Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex. Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II. Cham, 2014. pp. 115-125 (Lecture Notes in Computer Science).
@inproceedings{a075c9fca43341dd87ba7fc737c65a3d,
title = "Heuristics to Reduce the Number of Simplices 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. The refinement usually selects the first longest edge and ends when the size of the sub-simplices generated in the refinement is smaller than a given accuracy. Irregular sub-simplices may have more than one longest edge only for n¿=¿3. The question is how to choose the longest edge to be bisected such that the number of sub-simplices in the generated binary tree is minimal. The difficulty of this Combinatorial Optimization problem increases with n. Therefore, heuristics are studied that aim to minimize the number of generated simplices",
author = "G. Aparicio and L.G. Casado and B.G. T{\'o}th and E.M.T. Hendrix and I. Garc{\'i}a",
year = "2014",
doi = "10.1007/978-3-319-09129-7_9",
language = "English",
isbn = "9783319091280",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "115--125",
booktitle = "Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II",

}

Aparicio, G, Casado, LG, Tóth, BG, Hendrix, EMT & García, I 2014, Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex. in Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II. Lecture Notes in Computer Science, vol. 8580, Cham, pp. 115-125, 14th ICCSA 2014, Guimarães, Portugal, 30/06/14. https://doi.org/10.1007/978-3-319-09129-7_9

Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex. / Aparicio, G.; Casado, L.G.; Tóth, B.G.; Hendrix, E.M.T.; García, I.

Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II. Cham, 2014. p. 115-125 (Lecture Notes in Computer Science; Vol. 8580).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex

AU - Aparicio, G.

AU - Casado, L.G.

AU - Tóth, B.G.

AU - Hendrix, E.M.T.

AU - García, I.

PY - 2014

Y1 - 2014

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. The refinement usually selects the first longest edge and ends when the size of the sub-simplices generated in the refinement is smaller than a given accuracy. Irregular sub-simplices may have more than one longest edge only for n¿=¿3. The question is how to choose the longest edge to be bisected such that the number of sub-simplices in the generated binary tree is minimal. The difficulty of this Combinatorial Optimization problem increases with n. Therefore, heuristics are studied that aim to minimize the number of generated simplices

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. The refinement usually selects the first longest edge and ends when the size of the sub-simplices generated in the refinement is smaller than a given accuracy. Irregular sub-simplices may have more than one longest edge only for n¿=¿3. The question is how to choose the longest edge to be bisected such that the number of sub-simplices in the generated binary tree is minimal. The difficulty of this Combinatorial Optimization problem increases with n. Therefore, heuristics are studied that aim to minimize the number of generated simplices

U2 - 10.1007/978-3-319-09129-7_9

DO - 10.1007/978-3-319-09129-7_9

M3 - Conference contribution

SN - 9783319091280

T3 - Lecture Notes in Computer Science

SP - 115

EP - 125

BT - Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II

CY - Cham

ER -

Aparicio G, Casado LG, Tóth BG, Hendrix EMT, García I. Heuristics to Reduce the Number of Simplices in Longest Edge Bisection Refinement of a Regular n-Simplex. In Proceedings of the Computational Science and its Applications - ICCSA 2014, Part II. Cham. 2014. p. 115-125. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-09129-7_9