In this paper we introduce a new class of binary matrices whose entries show periodical configurations, and we furnish a first approach to their analysis from a tomographical point of view. In particular we propose a polynomial-time algorithm for reconstructing matrices with a special periodical behavior from their horizontal and vertical projections. We succeeded in our aim by using a reduction involving polyominoes which can be characterized by means of 2 − SAT formulas.
An introduction to periodical discrete sets froma tomographical perspective / A. FROSINI; M.NIVAT; L.VUILLON. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 347/1-2:(2005), pp. 370-392.
An introduction to periodical discrete sets froma tomographical perspective
FROSINI, ANDREA;
2005
Abstract
In this paper we introduce a new class of binary matrices whose entries show periodical configurations, and we furnish a first approach to their analysis from a tomographical point of view. In particular we propose a polynomial-time algorithm for reconstructing matrices with a special periodical behavior from their horizontal and vertical projections. We succeeded in our aim by using a reduction involving polyominoes which can be characterized by means of 2 − SAT formulas.
| File | Dimensione | Formato | |
|---|---|---|---|
|
[13].pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
245.86 kB
Formato
Adobe PDF
|
245.86 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
