About the Decidability of Polyhedral Separability in the Lattice $\mathbb {Z}^d$: Recognizing Digital Polyhedra with a Prescribed Number of Faces

Abstract : The recognition of primitives in digital geometry is deeply linked with separability problems. This framework leads us to consider the following problem of pattern recognition : Given a finite lattice set S ⊂ Z^d and a positive integer n, is it possible to separate S from Z d \S by n half-spaces? In other words, does there exist a polyhedron P defined by at most n half-spaces satisfying P ∩Z^d = S? The difficulty comes from the infinite number of constraints generated by all the points of Z^d \ S. It makes the decidability of the problem non straightforward since the classical algorithms of polyhe-dral separability can not be applied in this framework. We conjecture that the problem is nevertheless de-cidable and prove it under some assumptions: in arbitrary dimension, if the interior of the convex hull of S contains at least one lattice point or if the dimension d is 2 or if the dimension d = 3 and S is not in a specific configuration of lattice width 0 or 1. The proof strategy is to reduce the set of outliers Z^d \ S to its minimal elements according to a partial order "is in the shadow of ". These minimal elements are called the lattice jewels of S. We prove that under some assumptions, the set S admits only a finite number of lattice jewels. The result about the decidability of the problem is a corollary of this fundamental property.
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download

https://hal.uca.fr/hal-02023867
Contributor : Yan Gerard <>
Submitted on : Monday, February 18, 2019 - 5:22:49 PM
Last modification on : Monday, January 20, 2020 - 12:14:05 PM
Long-term archiving on: Sunday, May 19, 2019 - 5:53:35 PM

File

Gerard.pdf
Files produced by the author(s)

Licence


Public Domain

Identifiers

Collections

Citation

Yan Gerard. About the Decidability of Polyhedral Separability in the Lattice $\mathbb {Z}^d$: Recognizing Digital Polyhedra with a Prescribed Number of Faces. Journal of Mathematical Imaging and Vision, Springer Verlag, 2017, 59 (1), pp.52-68. ⟨10.1007/s10851-017-0711-y⟩. ⟨hal-02023867⟩

Share

Metrics

Record views

50

Files downloads

60