Discrete Optimization: The Case of Generalized BCC Lattice

Gergely Kovács, Benedek Nagy, Gergely Stomfai, Neşet Deniz Turgay and Béla Vizvári
Additional contact information
Gergely Kovács: Department of Methodology of Applied Sciences, Edutus University, 2800 Tatabánya, Hungary
Benedek Nagy: Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta 99628, North Cyprus, Turkey
Gergely Stomfai: ELTE Apáczai Csere János High School, 1053 Budapest, Hungary
Neşet Deniz Turgay: Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta 99628, North Cyprus, Turkey
Béla Vizvári: Department of Industrial Engineering, Eastern Mediterranean University, Famagusta 99628, North Cyprus, Turkey

Mathematics, 2021, vol. 9, issue 3, 1-20

Abstract: Recently, operations research, especially linear integer-programming, is used in various grids to find optimal paths and, based on that, digital distance. The 4 and higher-dimensional body-centered-cubic grids is the n D ( n ≥ 4 ) equivalent of the 3D body-centered cubic grid, a well-known grid from solid state physics. These grids consist of integer points such that the parity of all coordinates are the same: either all coordinates are odd or even. A popular type digital distance, the chamfer distance, is used which is based on chamfer paths. There are two types of neighbors (closest same parity and closest different parity point-pairs), and the two weights for the steps between the neighbors are fixed. Finding the minimal path between two points is equivalent to an integer-programming problem. First, we solve its linear programming relaxation. The optimal path is found if this solution is integer-valued. Otherwise, the Gomory-cut is applied to obtain the integer-programming optimum. Using the special properties of the optimization problem, an optimal solution is determined for all cases of positive weights. The geometry of the paths are described by the Hilbert basis of the non-negative part of the kernel space of matrix of steps.

Keywords: integer programming; digital geometry; non-traditional grids; shortest chamfer paths; 4D grid; linear programming; optimization; digital distances; chamfer distances; weighted distances (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/3/208/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/3/208/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:3:p:208-:d:483815

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().