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 organized 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.
| 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 |
|