Optimal partial tiling of Manhattan polyominoes

Olivier Bodini; Jérémie Lumbroso

doi:10.1007/978-3-642-04397-0_8

Optimal partial tiling of Manhattan polyominoes

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Discrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings
Pages	79-91
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-04397-0_8
State	Published - 2009
Externally published	Yes
Event	15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009 - Montreal, QC, Canada Duration: Sep 30 2009 → Oct 2 2009

Publication series

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

Conference

Conference	15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009
Country/Territory	Canada
City	Montreal, QC
Period	9/30/09 → 10/2/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-04397-0_8

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

@inproceedings{7a76c713a7bd46c0b4855735834a6ed9,

title = "Optimal partial tiling of Manhattan polyominoes",

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.",

author = "Olivier Bodini and J{\'e}r{\'e}mie Lumbroso",

note = "Funding Information: Supported by ANR contract GAMMA, “G{\'e}n{\'e}ration Al{\'e}atoire Mod{\`e}les, M{\'e}thodes et Algorithmes”, BLAN07-2 195422.; 15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009 ; Conference date: 30-09-2009 Through 02-10-2009",

year = "2009",

doi = "10.1007/978-3-642-04397-0_8",

language = "English (US)",

isbn = "3642043968",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "79--91",

booktitle = "Discrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings",

}

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

Optimal partial tiling of Manhattan polyominoes. / Bodini, Olivier; Lumbroso, Jérémie.
Discrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings. 2009. p. 79-91 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5810 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimal partial tiling of Manhattan polyominoes

AU - Bodini, Olivier

AU - Lumbroso, Jérémie

N1 - Funding Information: Supported by ANR contract GAMMA, “Génération Aléatoire Modèles, Méthodes et Algorithmes”, BLAN07-2 195422.

PY - 2009

Y1 - 2009

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

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

UR - http://www.scopus.com/inward/record.url?scp=77952659681&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952659681&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04397-0_8

DO - 10.1007/978-3-642-04397-0_8

M3 - Conference contribution

AN - SCOPUS:77952659681

SN - 3642043968

SN - 9783642043963

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 79

EP - 91

BT - Discrete Geometry for Computer Imagery - 15th IAPR International Conference, DGCI 2009, Proceedings

T2 - 15th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2009

Y2 - 30 September 2009 through 2 October 2009

ER -

Optimal partial tiling of Manhattan polyominoes

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this