Fundamenta Informaticae - Volume 189, issue 2

Authors: Dulio, Paolo | Frosini, Andrea | Rozenberg, Grzegorz | Tarsissi, Lama

Article Type: Other

DOI: 10.3233/FI-222153

Citation: Fundamenta Informaticae, vol. 189, no. 2, pp. i-x, 2022

Authors: Ceko, Matthew | Hajdu, Lajos | Tijdeman, Rob

Article Type: Research Article

Abstract: Discrete tomography focuses on the reconstruction of functions from their line sums in a finite number d of directions. In this paper we consider functions f : A → R where A is a finite subset of ℤ2 and R an integral domain. Several reconstruction methods have been introduced in the literature. Recently Ceko, Pagani and Tijdeman developed a fast method to reconstruct a function with the same line sums as f . Up to here we assumed that the line sums are exact. Some authors have developed methods to recover the function …f under suitable conditions by using the redundancy of data. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than d /2 errors can be corrected and that this bound is the best possible. Moreover, we prove that if it is known that the line sums in k given directions are correct, then the line sums in every other direction can be corrected provided that the number of wrong line sums in that direction is less than k /2. Show more

Keywords: discrete tomography, error correction, line sums, polynomial-time algorithm, Vandermonde determinant

DOI: 10.3233/FI-222154

Citation: Fundamenta Informaticae, vol. 189, no. 2, pp. 91-112, 2022

Authors: Gerard, Yan

Article Type: Research Article

Abstract: We consider a class of problems of Discrete Tomography which has been deeply investigated in the past: the reconstruction of convex lattice sets from their horizontal and/or vertical X-rays, i.e. from the number of points in a sequence of consecutive horizontal and vertical lines. The reconstruction of the HV-convex polyominoes works usually in two steps, first the filling step consisting in filling operations, second the convex aggregation of the switching components. We prove three results about the convex aggregation step: (1) The convex aggregation step used for the reconstruction of HV-convex polyominoes does not always provide a solution. The example …yielding to this result is called the bad guy and disproves a conjecture of the domain. (2) The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. (3) With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the digital convex sets which are not fat remains an open question. Show more

Keywords: Discrete Tomography Polyomino Digital Convex sets Filling operations Switching Component

DOI: 10.3233/FI-222155

Citation: Fundamenta Informaticae, vol. 189, no. 2, pp. 113-143, 2022

Authors: Vincze, Csaba | Nagy, Ábris

Article Type: Research Article

Abstract: A distance mean function measures the average distance of points from the elements of a given set of points (focal set) in the space. The level sets of a distance mean function are called generalized conics. In case of infinite focal points the average distance is typically given by integration over the focal set. The paper contains a survey on the applications of taxicab distance mean functions and generalized conics’ theory in geometric tomography: bisection of the focal set and reconstruction problems by coordinate X-rays. The theoretical results are illustrated by implementations in Maple, methods and examples as well.1

Keywords: distance mean functions, generalized conics, taxicab distance, parallel x-rays

DOI: 10.3233/FI-222156

Citation: Fundamenta Informaticae, vol. 189, no. 2, pp. 145-169, 2022

Authors: Coluzzi, Davide | Baselli, Giuseppe

Article Type: Research Article

Abstract: Schizophrenia is a brain disorder leading to detached mind’s normally integrated processes. Hence, the exploration of the symptoms in relation to functional connectivity (FC) had great relevance in the field. Connectivity can be investigated on different levels, going from global features to single edges between pairs of regions, revealing diffuse and localized dysconnection patterns. In this context, schizophrenia is characterized by a different global integration with reduced connectivity in specific areas of the brain, part of the Default Mode Network (DMN). However, the assessment of FC presents various sources of uncertainty. This study proposes a multi-level approach for more robust …group-comparison. FC data between 74 AAL brain areas of 15 healthy controls (HC) and 12 subjects with chronic schizophrenia (SZ) were used. Multi-level analyses were carried out by the previously published SPIDER-NET tool. Graph topological indexes were evaluated to assess global abnormalities. Robustness was augmented by bootstrapped (BOOT) data and the stability was evaluated by removing one (RST1) or two subjects (RST2). The DMN subgraph was extracted and specifically evaluated. Changes relevant to the overall local indexes were also analyzed. Finally, the connection weights were explored to enhance common strongest activations/deactivations. At a global level, expected trends of the indexes were found and the significance of modularity (p = 0.043) was not confirmed by BOOT (p = 0.133). The robustness assessment tests (both RST1 and RST2) highlighted more stable results for BOOT compared to the direct data testing. Conversely, significant results were found in the analysis at lower levels. The DMN highlighted reduced connectivity and strength as well as increased deactivation in the SZ group. At local level, 13 areas were found to be significantly different (p < 0.05) in the groups, highlighting a greater divergence in the frontal lobe. These results were confirmed analyzing the single negative edges, suggesting inverted connectivity between prefronto-temporal areas. In conclusion, multi-level analysis supported by BOOT is highly recommended when analyzing FC, especially when diffuse and localized dysconnections must be investigated in limited samples. Show more

DOI: 10.3233/FI-222157

Citation: Fundamenta Informaticae, vol. 189, no. 2, pp. 171-198, 2022