Skip to Main content Skip to Navigation
Conference papers

The packing problem : A divide and conquer algorithm on cellular automata

Nicolas Bacquey 1, *
* Corresponding author
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : This paper introduces a new algorithm to deal with the packing problem on cellular automata of di- mension 2 in linear time complexity; which means O(n) for an input square picture of size n × n. We use a divide and conquer approach to achieve this linear time complexity. This algorithm pre- serves the black cells at each step of the algorithm, i.e. only moves them, which was the main design flaw in previous algorithms.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00957117
Contributor : Etienne Grandjean Connect in order to contact the contributor
Submitted on : Saturday, March 8, 2014 - 7:26:22 PM
Last modification on : Tuesday, October 19, 2021 - 11:34:56 PM
Long-term archiving on: : Sunday, June 8, 2014 - 10:42:43 AM

File

divide_and_conquer_packing.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : hal-00957117, version 1

Citation

Nicolas Bacquey. The packing problem : A divide and conquer algorithm on cellular automata. Automata & JAC 2012, Sep 2012, Cargese, France. pp.1-10. ⟨hal-00957117⟩

Share

Metrics

Record views

172

Files downloads

247