Open Problems in Digital Geometry an Topology

This list of open problems was first initiated during the winter school DIG'2000 at Dagstuhl/Germany. New problems were introduced during an open problems session oragnized during DGCI 2016. If you want to add new problems, feel free to send a pdf or simple html file

Responses or partial new results to the published problems are inserted into the table, next to the related problem. A response should also be in pdf format (about 2 pages) and may include links to further material.

Date Problem/Response (First) Author Links
9, May 2001 1 Surface Area Estimation Reinhard Klette CITR-TR-87
11, September 2001 1.1 Estimation algorithm and multigrid convergence proof David Coeurjolly Technical Report
10, May 2001 2 Superlinear Convergence for Length Estimation Reinhard Klette Citr-TR-87
22, June 2001 3 Axiomatic 3-D Digital Topology T. Yung Kong
21, August 2001 4 Binary Codes for Counting Digital Topologies Atsushi Imiya
11, September 2001 5 Minimal-Number DSS and DPS Segmentations Azriel Rosenfeld CITR-TR-93
27, January 2005 5.1 On the min DSS problem of closed discrete curves Fabien Feschet
4, May 2009 5.2 Minimum decomposition of a digital surface into digital plane segments is NP-hard Isabelle Sivignon
16, April 2002 6 MLP Linear-time 3D Length Estimation Thomas Buelow CITR-TR-55
17, February 2003 7 Connectivity Number Valentin Brimkov CITR-TR-125
23, April 2004 8 List collected on a 2004 Dagstuhl seminar Reinhard Klette
01, November 2004 8.1 Vertices of the digital line/(hyper)plane segment polytope Valentin E. Brimkov
01, November 2004 9 Convex digital curve segmentation Valentin E. Brimkov
13, December 2004 10 The convex skull problem Jean-Marc Chassery
4, May 2016 10.1 A good approximation of the convex skull (updated but still open) Gunilla Borgefors
15, January 2005 11 Animal and B-Problems Akira Nakamura
17, September 2007 12 Surface Area Estimation with Non-Cubic Voxels Nahum Kiryati
19, April 2016 13 Counting the number of k-dimensional grid cells of Zd that intersect a polytope J.-O. Lachaud
19, April 2016 14 Nivat-Vuillon Conjecture Yan GĂ©rard
19, April 2016 15 Lonely runner and view obstruction I. Sivignon
13, May 2016 16 Complexity lower bounds for DSS problems I. Sivignon
19, April 2016 17 Thickness diagram: complexity of the arrangement of balls of a digital set medial axis D. Coeurjolly
19, April 2016 18 Number of cuts of a hypervoxel by a hyperplane E. Andres
19, April 2016 19 3D Digital Straight Segment embedded in a given Digital Plane J.-O. Lachaud
20, September 2017 20 Analytical characterization of the 3D bijective digitized rotations Kacper Pluta link
20, September 2017 21 New digital plane thickness with unknown properties Eric Andres
20, September 2017 22 Does an unfolding of Menger1 pave space? Eric Andres


IAPR-TC18 webpage

Responsible for this page: tc18@tc18.org