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


IAPR-TC18 webpage

Responsible for this page: tc18@tc18.org