Skip to Main content Skip to Navigation

Convex Aggregation Problems in Z²

Abstract : We introduce a family of combinatorial problems of digital geometry that we call convex aggregation problems. Two variants are considered. In Unary convex aggregation problems, a first lattice set A ⊆ Z d called support and a family of lattice sets B i ⊆ Z d called pads are given. The question to determine whether there exists a non-empty subset of pads (the set of their indices is denoted I) whose union A∪i∈I B i with the support is convex. In the binary convex aggregation problem, the input contains the support set A ⊆ Z 2 and pairs of pads B i and B i. The question is to aggregate to the support either a pad B i or its correspondent B i so that the union A ∪i∈I B i ∪ i ∈I B i is convex. We provide a first classification of the classes of complexities of these two problems in dimension 2 under different assumptions: if the support is 8-connected and the pads included in its enclosing rectangle, if the pads are all disjoint, if they intersect and at least according to the chosen kind of convexity. In the polynomial cases, the algorithms are based on a reduction to Horn-SAT while in the NP-complete cases, we reduce 3-SAT to an instance of convex aggregation.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.uca.fr/hal-02091208
Contributor : Yan Gerard <>
Submitted on : Friday, April 5, 2019 - 2:54:21 PM
Last modification on : Wednesday, March 4, 2020 - 12:28:02 PM

File

DGCI_2019_convex_aggregagtion....
Files produced by the author(s)

Licence


Distributed under a Creative Commons CC0 - Public Domain Dedication 4.0 International License

Identifiers

Collections

Citation

Yan Gérard. Convex Aggregation Problems in Z². 21st IAPR International Conference, DGCI 2019,, Mar 2019, Marne la Vallée, France. ⟨10.1007/978-3-030-14085-4\_34⟩. ⟨hal-02091208⟩

Share

Metrics

Record views

31

Files downloads

31