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.

• Progress: not really, the case of 2 known blue points + 2 unknown red points in 1d seems easy.

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.

•     Coordinator: Jyoti, Nishat. Other people involved: S. Felsner, S. Kobourov, W. Evans, M. Kaufmann, Kevin Verbeek.  Fan supporters: Bill Lenhart, Rob Hochberg, Sylvain Lazard, Sue Whitesides
• Progress: nxm tables with convex quadrants. Solution for outer rectangle, convex quadrilateral, (convex?) n-gon n>4, circle with circular arcs inside, sphere.
Open problems: air pressure proof. In 3D, eg 2x2x2 box.
•      Solution for a 2xn table. consider an infinite parallel-axis rectangle of height 2. On the top edge draw segments of length the area of the top row of the table. Similarly, on the botton edge, draw segments of length the area of the bottom row of the table. Connect the vertices, defining trapezoids and triangulate them. This gives a set of triangles whose area are the values in the table. However the top and bottom side have different length (in general). Assuming that sum of the bi (bottom row) is larger or equal than the sum of the ai (top row), consider trapezoids defines by the 4 triangles b_ia_ia_{i+1}{b_{i+1}. The area of this trapezoid is the sum of the area of b_ia_ia_{i+1}{b_{i+1} and it does not change by shrinking the bottom two edges and enlarging the top two edge as long as the sum of the lengths of the four edges does not change. While this trapezoid deforms, the inner cells deform so that their areas do not change. The other trapezoids deform while their top and bottom edge translate but their area remains unchanged.  Eventually, the top and bottom sides have the same length which concludes the construction.
• Solution for the nxm rectangle. Split the table in two parts so that the area are the same above and below (possibly cutting a row into 2). In each of the sub-tables sum the values in the columns. This gives a 2xn table. Apply the algorithm for 2xn tables and for each cell, divide it in a simple manner into m/2 regions of the correct area (for instance for a triangle, draw m/2-1 edges from one of the vertices.
• Solution for any atrbitrary polygon: if it is a rectangle, we can do it. If it is an n-gon when n>4, then there isn't always a solution.
• In a circle with circular arcs. It is not always possible to draw the cartogram of the table in a circle with straight lines
• On a sphere with spherical straight lines
• Open problem 1: Find a proof for arbitrary quadrangle using air pressure technique
• Open problem 2: Solve 2x2x2

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?

• Coordinator: Jyoti. Other people involved: Beppe, Bill, Nishat, Zahed.
• Progress. Known: Planar cubic graphs drawable with 4 slopes if allowing crossing and 6 slopes otherwise. Plane 3-tree it is possible with the max-degree^5 sloples, and outerplanar graphs with delta-1 slopes.
• New results. On Halin graphs (a tree where all the leaves are connected in a cycle) with delta+3 slopes.

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.

• Coordinator: Dominique Attali. People involved Olivier Devillers, Marc Glisse, Sylvain Lazard. Friend: Ulrike Stege
• Progress: The current idea is to use a contractible modified torus (add two faces to fill the loops and make a hole) whose triangulation has few neat  edge contractions. On the variable gadget we have to identify a "true"and a "false" edges  that are neat-contractable (but not both at the beginning) and a lock that is neat-contractable and allow the neat-contraction of the second edge. On the clause gadget we need three neat-contractible edges for the litterals and a key that is not neat-contractible until one of the litteral has been contracted.

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

• Coordinator: Carola Wenk. People involved: Helmut Alt, Friends: Sylvain Lazard, Michael Kaufmann, Will Evans, Sue Whitesides
• Progress: Example of two curves where the solution with one curve (f'=g') is distinct from the two curves problems. The problem with one curve seems quite difficult because one actually wants a simple curve f'=g' which makes the problem more complicated.

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.

• Coordinator: Tamara. People involved: Bill Lenhart, Beppe Liotta, Micheal Kaufmann, Will Evans, Steve Wisath Fan supporters: Sue Whitesides, Laurie Heyer.
• Progress. Some remarks
• Strong Bar-1 Visibility: If two bars are either directly (empty rectangle of epsilon-width between the bars) or indirectly (epsilon-width rectangle may intersect a single, third bar) then the edge between the two bars must exist in the graph
• Subclasses based on stabbing bars by vertical lines:
• Maximum of two bars stabbed by any vertical line:  This is exactly the class of catepillars.  Note that these are the only triangle-free strong bar-1 visibility graphs
• Max. of 3 bars stabbed: These are the "fat caterpillars" in which any leg can be replaced by an "augmented" fan of triangles and any segment of the spine can be replaced by an "augmented" path of triangles.  Augmented means that any internal edge can have a set of triangles attached to it.
• Max. of 4 bars is mostly completely characterized: stay tuned

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?

• Progress: For the number of connected components, the total persistence is the length of the MST that is bounded by O(n^{1-1/d}).  For the cavities, we match a cavity with a certain volume so that the persistence of a cavity can be split in "element of persistence". The sum of "element of persistence"to the power d is then bounded by a constant and we get by Cauchy-Schwartz that the number of cavities is O(n^{\floor{d/2}^(1-1/d)}).
• Coordinator: Marc. People involved: Dominique, Olivier, Sylvain.

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 ?

• Coordinator: Marc Glisse People involved: Zahed Rahmati, Olivier Devillers, Raimund Seidel, Sylvain Lazard, Dominique Attali. Friend of spanners: Christian Knauer.
• Progress: We got a lower bound that Delaunay cannot be better than a \frac{\pi}{\sqrt{2}} spanner. The example is a suitable quadrilaterization of the sphere with tiles that are close to squares. The factor is obtained as the product of (i) a factor pi/2 for the ration of the length of a half great circle over the diameter of the sphere and (ii) a factor sqrt{2} that corresponds to the zigzags detour that are made along this great circle because of the suitable quadrilaterization of the sphere. Then a perturbation ensure a unique Delaunay triangulation that produce the desired ratio. Using a similar argument, for L_infty, we can get a lower bound of 2.61*sqrt(2), that is 3.6.

Ulrike Stege. Building Wiring Design
From http://www.ics.uci.edu/~eppstein/200-f01.pdf
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 http://www.cs.berkeley.edu/~smaji/reports/bwp-note.pdf

• People involved: Rob, Ulrike, Helmut Raimund Christian Zahled Sue Carl Laurie Carola
• Can be done
• for a n by n grid of a times b
• brickwall with tiles 1 by 2 (wires of length 1, so length = # wires)
• conjecture : needs # faces - 3 wires (does not work, counter example)
• rectilinear drawing of degree 3, minimum number of wires is # blocks -2
• next step : short total length