IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v38y2019i3d10.1007_s10878-019-00425-x.html
   My bibliography  Save this article

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

Author

Listed:
  • Gergely Kovács

    (Edutus University)

  • Benedek Nagy

    (Eastern Mediterranean University)

  • Béla Vizvári

    (Eastern Mediterranean University)

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.

Suggested Citation

  • Gergely Kovács & Benedek Nagy & Béla Vizvári, 2019. "Chamfer distances on the isometric grid: a structural description of minimal distances based on linear programming approach," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 867-886, October.
    • Handle: RePEc:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00425-x
    DOI: 10.1007/s10878-019-00425-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-019-00425-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-019-00425-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Benedek Nagy & Bashar Khassawneh, 2020. "On the Number of Shortest Weighted Paths in a Triangular Grid," Mathematics, MDPI, vol. 8(1), pages 1-16, January.
    2. Gergely Kovács & Benedek Nagy & Gergely Stomfai & Neşet Deniz Turgay & Béla Vizvári, 2021. "Discrete Optimization: The Case of Generalized BCC Lattice," Mathematics, MDPI, vol. 9(3), pages 1-20, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00425-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.