Chamfer distances on the isometric grid: a structural description of minimal distances based on linear programming approach

Gergely Kovács (), Benedek Nagy () and Béla Vizvári
Additional contact information
Gergely Kovács: Edutus University
Benedek Nagy: Eastern Mediterranean University
Béla Vizvári: Eastern Mediterranean University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 13, 867-886

Abstract: Abstract Chamfer distances on the isometric grid are considered. A new method to compute the chamfer distances based on linear optimization is presented. In the LP model the starting pixel is the Origin, that is a triangle of the grid having co-ordinates (0, 0, 0). The co-ordinates of the end pixel of the path give the right-hand side of the model. The variables are the used numbers of the elementary steps. Each type of an elementary step has a uniquely defined weight. Our operational research approach determines the optimal paths as basic feasible solutions of a linear programming problem. We give directed graphs with feasible bases as nodes and arcs with conditions on the used weights such that the simplex method of linear programming may step from one feasible basis to another feasible basis. Thus, the possible course of the simplex method can be followed and the optimal bases can easily be captured. Thus, the final result of the analysis is an O(1) checking of the feasibility and optimality conditions. The optimal bases are summarized in a theorem which is the consequence of the general theory of linear programming. The method can be applied for other grids, but it needs to be adjusted for the particular grid.

Keywords: Chamfer distances; Weighted distances; Optimization; Shortest paths; Linear programming; Digital geometry; Non-traditional grids; 52B05; 68U10; 52C99; 90C05 (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00425-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00425-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00425-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().