Optimal partial tiling of Manhattan polyominoes

Olivier Bodini, Jérémie Lumbroso

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Finding an efficient optimal partial tiling algorithm is still an open problem. We have worked on a special case, the tiling of Manhattan polyominoes with dominoes, for which we give an algorithm linear in the number of columns. Some techniques are borrowed from traditional graph optimisation problems.

Original languageEnglish (US)
Title of host publicationDiscrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings
Pages79-91
Number of pages13
DOIs
StatePublished - 2009
Externally publishedYes
Event15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009 - Montreal, QC, Canada
Duration: Sep 30 2009Oct 2 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5810 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009
CountryCanada
CityMontreal, QC
Period9/30/0910/2/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal partial tiling of Manhattan polyominoes'. Together they form a unique fingerprint.

  • Cite this

    Bodini, O., & Lumbroso, J. (2009). Optimal partial tiling of Manhattan polyominoes. In Discrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings (pp. 79-91). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5810 LNCS). https://doi.org/10.1007/978-3-642-04397-0_8