Workshop on Computational Geometry -- Barbados Feb 2-8 2013

Open problems

Olivier Devillers. Online matching of boxes and tops. Given a set of boxes and box tops we want to match the tops to the boxes. Using  say minimum matching between a set of blue points and a set of red points, we can find a "good" matching that minimizes some criterion. Now the real problem is that the factory is continuously producing boxes and tops and we have a batch of k of each so every time a new box and top arrive, one box and top from the batch have to be matched. 

Stefan Felsner. Table cartogram. Input: table of numbers. In the rectangle (formed by the table), is it possible to distort the cells (ie move the vertices -- except the that the outer boundary remains the input rectangle) so that the area of every cell is the value of the input table (assuming that the sum of the values is the area of the rectangle). It is known that it is possible if one allows the vertices on the rectangle edges can move freely.

     Open problems: air pressure proof. In 3D, eg 2x2x2 box. 
Stephen Kobourov. Area universal layout.   Variant of the previous problem. Here, every cell should remain parallel axis. As above the topology should be preserved. Such a drawing is not alwalys possible but there is characterization of when it is possible, ie for every maximal (horizontal or vertical) segment, there should be only one cell on one side. Question: can such a drawing be computed in polynomial time.

Beppe Liotta. Quasi-planar slope number. Quasi planar drawing (no 3 edges pairwise intersect). K-planar (no edge is intersected by more than k edges). The slope number is the minimum number of slopes for drawing a graph. For a planar graph of degree d the slope number is lower bounded by a^d  in the worst case (for some constant a). For 3-trees, it is possible to draw the graph with d^5 slopes. What is the mimimum slope number for quasi-planar, K-planar, etc?  For example for a planar 3-tree with maximum vertex degree d?

Dominique Attali. 3D complex or Rips  complex neat reducibility. We are interested in simplifying a simplicial complex with elementary operations such as edge contractions. The contraction of the edge ab to the vertex c is the operation that identifies the vertices a and b to the vertex c. If the edge ab satisfies the link condition Link(ab)=Link(a) cap Link(b), then its contraction preserves the  homotopy type. An edge contraction ab is called neat if ab satisfies the link condition. We would like to establish for neat edge contractions results similar to those known for elementary collapses. An elementary collapse is the operation that removes a pair of simplices assuming one of the two simplices is the unique proper coface of the other. An elementary collapse is also a homotopy-preserving operation.

Known result [Martin Tancer 2012]: It is NP complete to decide whether a 3D simplicial complex can be reduced to a point by a sequence of elementary collapses.

Question: Is it NP-complete to decide whether a 3D simplicial complex can be reduced to a point by a sequence of neat edge contractions.

Rips complex: given a set of points P, consider the proximity graph induced by placing balls of radius alpha at every point. The Rips complex is all the cliques of the proximity graph.

Known result: If P is not too far from a convex set (roughly speaking it samples well a convex set) then the Rips complex of P with parameter alpha can be reduced to a point by a sequence of elementary collapses (for a well-chosen alpha). 

Question. Under the same condition on P (well sampling of a convex set) and the same condition on alpha, is there a sequence of neat edge contractions that reduces the Rips complex of P with parameter alpha to a point. 

Raimund Seidel. Bounded-degree triangulation counting. T(P) is the number of triangulations of a point set P of cardinality n in 2D. Td(P): same thing but with maximum degree d. We know how to compute the first one in 2^n time (precisely Theta(n^2 2^n)). Note that the number of such triangulation is much larger (at least 27^n)  Problem: compute the latter in less than d^n.

Raimund Seidel. Upper bound on the number of triangulation via visibility graph. The best known upper bound for T(P) is 30^n. Can we do better by using the fact that given a triangulation there is an algorithm (Tamassia, Steve Wismath et al)  that construct a set of edges so that  its vertical visibility graph is the triangulation. 

Michael Kaufmann. Drawing RACs with 3 bends per edges in optimal area. Known results:
Planar graphs: m<=3n-6. 
RAC (right angle crossings): m<=4n-10.
RAC with one bend per edge: m=O(n^?)
RAC with 2 bends per edges: m=O(n^{7/4})
RAC with 3 bends per edges: Kn and there is a construction that uses O(n^4) area.
RAC with 4 bends per edges: Kn and there is a construction that uses O(n^3) area.
Question: Is this optimal? 

Carola Wenk. Flippy Frechet distance.
Given 2 curves f and g with same endpoints and f above g (where above is to be defined appropriately). Find curves f' and g' with same endpoints and f' below g' such that they minimize the max of the Frechet distances between f and f' and between g and g'. It is not known whether one minimum is realized with f'=g'. 

Christian Knauer. Approximation algorithm for maximum-size convex subset of points in 3D.
Givem n point in R3. What is the largest subset C of P in convex position.
Known: NP-hard, W[1]-hard. There always exists a subset C of size Theta(log n)  
Problem: approximation algorithm? There exists a Theta(n/log n) approx factor in poly time

Will Evans. Bar 1-visibility graphs
G+=G+s and connect s to every ariticulation point.
G+ is planar iff G is bar-visibility graph (a bar-visibility graph is a graph whose vertices can be represented by vertical segments that are connected by edges iff they are horizontaly visibles) 

Question: Characterize bar 1-visibility graphs (vertical segments are slightly transparent so that one can see through 1 segment but not through 2 of them). Consider Strong  bar 1-visibility graphs: if two segments see each other (possibly trhough another edge), there must be an edge in the corresponding graph.

Marc Glisse. Total persistence for 3D Delaunay triangulation.
Measure of simplices. 
Segment: length/2
triangle: obtuse: measure = 0. Acute : circomscribing radius - max measure of segments
We grow disks around vertices. For acute triangles, at one point the three disks define a hole . We are interested in the life-expectency of that hole (or persistence) 
For tetrahedra, if the center of the circomscribing sphere is outside of the tetrahedron we set the measure to 0, otherwise, we take the radius minus max of the measures of its faces. 

For n points in 3D on 2 segments so that the Delaunay triangulation has size n^2 its seems that the total persistence is O(1). For points uniformly distributed in a ball, the total persistence (seems to be) n times 1/cubic root of n. 
Question:  can we bound the total persistence?

Marc Glisse. 3D Delaunay spanner.
Delaunay is known to be a t-spanner in 2D. 
For L_2 Delaunay [Xia; SoCG'11], it is known that t<1.98 and there exists counter example that prove that t>Pi/2+0.01
For L_1- and L_infty-Delaunay [Bonichon et. al.; ESA'12], the stretch factor is \sqrt{4+2\sqrt{2}}= 2.61

What about 3D ? Is Delaunay a t-spanner for some constant t ?

Ulrike Stege. Building Wiring Design
Given a rectangle partitioned into smaller rectangles. Find a tree touching each rectangle (including outer one). Tree edges must lie along rectangle sides. Minimize total length.

no algorithm known (not even guaranteed approx. ratio). NP-complete?
An NP-complete variant can be found in