Informatica logo


Login Register

  1. Home
  2. Issues
  3. Volume 26, Issue 1 (2015)
  4. On the Minimum Number of Simplex Shapes ...

Informatica

Information Submit your article For Referees Help ATTENTION!
  • Article info
  • Related articles
  • Cited by
  • More
    Article info Related articles Cited by

On the Minimum Number of Simplex Shapes in Longest Edge Bisection Refinement of a Regular n-Simplex
Volume 26, Issue 1 (2015), pp. 17–32
Guillermo Aparicio   Leocadio G. Casado   Eligius M.T. Hendrix   Boglárka G.-Tóth   Inmaculada Garcia  

Authors

 
Placeholder
https://doi.org/10.15388/Informatica.2015.36
Pub. online: 1 January 2015      Type: Article     

Received
1 January 2014
Accepted
1 August 2014
Published
1 January 2015

Abstract

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≥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.

Related articles Cited by PDF XML
Related articles Cited by PDF XML

Copyright
Vilnius University

Keywords
regular simplex longest edge bisection branch-and-bound combinatorial optimization simplex shape

Metrics
since January 2020
1480

Article info
views

0

Full article
views

598

PDF
downloads

248

XML
downloads

Export citation

Copy and paste formatted citation
Placeholder

Download citation in file


Share


RSS

INFORMATICA

  • Online ISSN: 1822-8844
  • Print ISSN: 0868-4952
  • Copyright © 2023 Vilnius University

About

  • About journal

For contributors

  • OA Policy
  • Submit your article
  • Instructions for Referees
    •  

    •  

Contact us

  • Institute of Data Science and Digital Technologies
  • Vilnius University

    Akademijos St. 4

    08412 Vilnius, Lithuania

    Phone: (+370 5) 2109 338

    E-mail: informatica@mii.vu.lt

    https://informatica.vu.lt/journal/INFORMATICA
Powered by PubliMill  •  Privacy policy