Bellairs CG workshop 1-7 Feb 2014
Open problem session (Saturday 1st, morning session)
Status report seesion (Monday 3rd, morning session)
Wrap up (Thursday 6th, evening session)
1) Christian Knauer. Largest (empty) convex polytope in R3.
Given n points in R3.
Find largest subset of points that are in convex position (or convex and empty of points).
Two possible measure: cardinality or volume.
Known in 2d (quadratic?).
NP hard in 3d. ⇒ Find a good approximation (in polynomial time)
2) Dave Bremner. Minimum norm point on a convex hull
Given a set of points in convex position such that the origin lies in the convex hull
Find a point on the convex hull that is closest to the origin
Known : NP hard in arbitrary dimension.
Question: Find something better than brute force (in medium dimension)
3) Guillaume Moroz. Integral of piecewise linear functions
Given: two piecewise linear functions in 3 variables f(x,y,z) and g(x,y,z), each defined on a domain D, but with different tetrahedrization of D for each function.
Problem: Compute the integral of fg or (fg)^2 over D in sub-quadratic time
Or reduce the 3-sum problem to this one. (Recall 3-sum: given n integers, is there three that sum to 0 - conjectured to be quadratic)
Christian: if domain is not connected Omega(n^{3/2}) by equivakence to Hopcroft's problem.
Hopcroft's problem:
Given n points and n hyperplanes decide if there is one point on one hyperplane.
There is a lower bound Omega(n^{3/2}).
Now let f (resp. g) be the characteristic functions of the hyperplanes (resp. points),
then int fg should allow to decide and we get the lower bound
Christian says: As Mark and Raimund remarked this is bogus: In that case the complexity of the domain is more like n^3 ...
Wrap up: no more news.
4) Beppe Liotta. Simultaneous embedding of three (labelled) path graphs
Let authorize a bit of crossing in the drawings of planar graph.
Consider path-graphs
Known : - Given two path graphs, there always a crossing-free simultaneous embedding
- For 3 path graphs, some crossing may be required.
Question: Is there a constant c such that it is always possible to simultaneous embed 3 path graphs with at most c crossing per edge? Ideal goal: c=1.
People involved: Beppe, Steve, Ulrike, Sue, Nishat, Sariel
The problem remains interesting if c, instead of being a constant, is sublinear (i.e. there is a sublinear number of crossing for every edge)
Graph theory approach: Is the union graph of 3 paths a c-planar graph?
Sariel points out that the graph theory approach has no hope because
for the graph formed by the union of 3 random matchings is an expander which has Theta(n^2) crossing with high probability. So there exists 3 paths for which their union graph has Theta(n^2) crossing.
Combinatorial approach: Given three permutations (corresponding to the 3 paths), find a fourth permutation so that if u and v are consecutive in any of the 3 permutations, then u and v are distance at most c in the fourth one.
Interestingly, even for 2 permutations (instead of 3) and with c=sqrt(n), the problem is not obvious (and open to us -- but not to Sariel by the look of things;) )
Wrap up. Simplified the problem by considering 3 matchings instead of 3 paths. It is possible to embbed 3 matchings without crossing (within each crossing). The intetresting thing about it is that it does not work for any point set. On other words, the geometry of the point set has to be considered, not only the combinatorics.
5) Mark de Berg. Complexity of the union of cigars
Consider n segments in 2D and a set of n radii, each assigned to a segment, and their Minkovski sums (defining n cigars)
- If all the disk radii are the same, the complexity of the union is linear.
- given n close parallel segments with small associated radii and n orthogonal segment whose associated cigars intersect all small one, gives complexity Theta(n^2) for the union.
Given a random permutation of the radii, what is the expected complexity of their union
Known to be O(n log n) (paper by Pankaj, Sariel et al.)
Known to be in O(n log^3 n) if convex sets are considered instead of segments.
6) Michael Sagraloff. Bounds on isotopic triangulations of surfaces
Given a polynomial f(x,y,z) of degree n. What is the mimimum size of a triangulation that is isotopic to the surface? Where vertices are required or not to lie on the surface.
Known O(n^5) and Omega(n^3) with no constraint on the vertices (lower bound eg product of n planes)
If the points are required to lie on the surface, the best upper bound is O(n^7).
Solved in 2D: Theta(n^2) and Theta(n^3) for the relaxed and non-relaxed problems
Some effort have been made but so far without success
People involved: Christian, Guillaume, Marc, Sylvain, Olivier, who else?
7) Ioannis Emiris. Approximate decomposition of 2D Minkowski sums
Minkowski sum of 2 (convex) polygons in 2D is O(n).
Reverse problem:
Given a convex polygon with n integral vertices, its decomposition to a sum of 2 lattice polygons, one of complexity k, we showed it is solvable in roughly n^[k/2] by connecting it to the k-Sum problem. If one is a triangle (k=3), it amounts to 3-sum.
NP-hard if the complexity of the polygons is not given.
Problem: Define an approximation criterion and solve the epsilon-approximation in poly-time.
Some effort has been made: Coresets approximate input n-gon P by (1/eps)-gon Q s.t. along any direction, their widths have relative error < (1+eps). We can try all (exact) decompositions of Q in roughly (1/eps)^{1/2eps}.
How good are the obtained summands wrt P?
People involved: Mark. who else?
8) Christian Knauer. Partition of a point set that results in minimum Hausdorff distance
2 points sets, a red and a blue one, their Hausdorff distance can be computed.
Now, given 2n uncolored points, find a partition into red and blue so that their Hausdorff distance is minimized. (Other distances can be considered)
Reformulated the question with a parameter k: partition the set P of points into k subsets P1,...,Pk such that the maximum of the Hausdorff distance between every pairs Pi,Pj is minimized
Current results:
Approach: build a r-net with r=Opt (the maximum over every point of the distance to the other points) or 2*Opt for k>2
r-net: minimum set of disks of radius r centered on some vertices of P, such that the union contains all points. Since r=Opt, every disk contains at least one point (other than its center). For the unbalanced version and k=2, simply color the centers red and the other points blue.
For the balanced version and k=2. Consider every connected component of the MST of the graph that contains all edges shorter than Opt.
The r-net can be computed in linear time and Opt can be search among the n^2 pair distances.
People involved: Mark, Sariel, Dominique, Christian, Helmut, Carola.
Wrap up. Added Np-hardness in 3D.
9) Guillaume Moroz. Number of roots of the shifted product of two sparse univariate polynomials
Given two sparse univariate polynomials f(x) and g(x) of degree n with at most k non-zero coeffecients each. By Descarte’s rule, they each have at most 2(k-1)+1 roots, say 2k for simplicity.
Consider the product of fg. They trivially have at most 4k roots. However, Descartes rule gives an upper bound of 2k^2 roots (or 2n)
Question: find a non-trivial bound of roots of fg+1=0, that is an upper bound that is linear in k or lower bound that is quadratic in k.
This question is a specific case of the real tau conjecture, studied intensively by P. Koiran and his colaborators for its applications in complexity theory. The specific case asked here is refered in their work as first asked by Arkadev Chattopadhyay.
Approach 1. Consider h(x,y)=f(x)*g(y)-1. Consider the partition of the xy-plane by the x-roots of f and y-roots of g. In each rectangle, the function f(x)g(y) is morally convex, so it is (morally) intersected by the plane z=1 in a convex curve; when intersecting these curves by the lines x=y, we obtain O(k) intersections.
Approach 2. Using Descarte’s algorithm on polynomial f, we can partition the x-axis into O(k) intervals so that the number of change of sign of (the transformation of) f is 0 or 1. This property is not trivial and comes from the fact that when bisecting an interval where there are k change of sign, until it splits in intervals where the number of change of signs is less than k, we can merge the intervals with 0 change of sign, resulting into at most 4 intervals, 2 with 0 change of signs and two whose number of change of signs sum up to at most k. Furthermore, the intervals where f has one change of sign can be refined arbitrarily, preserving the property that we have in total O(k) intervals with 0 or 1 change of sign.
Doing the same thing for g, this partition the x-axis into O(k) intervals. The intervals containing a root of f or g are arbitrarily small so fg is also arb. small and fg+1 does not vanish. On the other intervals both (transform) of f and g have no change of sign. So fg (or -fg) only have positive coefficients. Now we add or substract 1 or -1; actually, it’s not \pm 1 but its transform through the mapping (for H_I(x) = (x+1)^{2n}(fg+1)[(ax+b)/(x+1)] = f_I(x)*g_I(x) + (x+1)^{2n} where f_I and g_I are the transformed of f and g over the interval I=[a,b] and have all positive or all negative coefficients.
Now considering the polynomials in the Bernstein basis . They have the property that adding/removing (x+1)^{2n} ammounts to add/remove 1 to every coefficients. Still if the coefficients are close to 1, removing 1 may change the signs…
Approach 3. Sparse multivariate representation
Represent the problem as a multivariate sparse system, such as $f-y=g-z=yz+1=0$. Then try to use results for such systems, such as [Avendano], [Koiran et al.],... that states that any lines intersect a bivariate sparse polynomial with $k$ monomials in at most $6k$ real roots.
Approach 4. Moment curve.
Let $B_f, B_g, B_{fg}$ be the respective monomial bases $(x^d_1,
\ldots, x^d_k)$, $(x^{e_1}, \ldots, x^{e_k})$ and
$(x^{d_i+e_j})_{1\leq i,j\leq k})$. The family of polynomials of the
form $fg+1$ can be seen as a variety $\mathcal V$ of dimension $2k$ in
the space of generic polynomials of the form $h+1$ of dimension $k^2$.
The discriminant $\mathcal D$ of $h+1$ is a hypersurface in $\mathbb R^{k^2}$. In each discriminant chamber
(connected components of $\mathbb R^{k^2}\setminus \mathcal D$), the number of real
solutions of $h$ is constant. The question can then be reformulated
as: what are the discriminant chambers intersected by $\mathcal V$.
For example, let $N$ be the number of times the curve $(1-t)\cdot 1 + t\cdot(fg+1)$
intersect $\mathcal D$. Then, morally, the number of real roots of $fg+1$ is
less or equal to $2N$, since the number of real roots morally increases at
most by $2$ after each crossing of the discriminant variety.
People involved: Christian, Guillaume, Ioannis, Michael, Marc, Olivier, Raimund, Sylvain
Wrap up. No solution yet. To be noted easier problems: f(xˆd1)g(xˆd2)+1 or even f(x)f(-x)-1=0. Observe that for f(x)ˆ2-1= 0 we have a solution because it factorizes into (f-1)(f+1)=0 ;).
10) Sariel Har-Peled. Approximation algorithm for smallest balls intersecting k segments
Given n segments in 2D or 3D and k<n.
Compute a smallest ball that intersects (at least) k segments
Known. If the question is asked for containment instead of intersection, approximation can be found in linear time.
11) Ioannis Emiris. Approximate nearest neighbor for hyperplane queries
Given n points in d dimensions. Determine a data structure for approximate nearest neighbor, where the queries are hyperplanes. Space usage should be O(n).
Query is a hyperplane, determine approximate closest or farthest nearest neighbor point in order log n time. We are interested in a practical solution, say, for d>20.
12) Ioannis Emiris. Embeddings of rigid graphs
A n-vertex graph is (minimally generically) rigid in the plane iff it contains 2n-3 edges: this is the Laman condition. The corresponding Cayley-Menger matrix has dimension n+1, with entry (i,j) containing dist(i,j)^2/2, for i,j=1..n, and an additional row and column of 1’s, where all diagonal entries are 0. If the graph is embeddable in d-dim Euclidean space then its rank = d+2. For computing the number of planar embeddings, we wish to find k vanishing minors (of size >=5) that contain k unknown distances (so as to have a square system) such that the union of all minors covers all Laman edges (so as to be 0-dimensional). The Mixed volume will hopefully give better upper bounds on the number of embeddings than 4^n which is known. The best lower bounds are about 2.5^n.
We can assume no degree-2 vertex is in the graph nor any 4-clique. Also the “maximal” graph should not include 2 triangles sharing a common edge.
Polynomial systems yielding optimal Mixed Volume are known for up to n=8, of size n-3 for n<8, or n-2 for n=8. All equations are 5x5 minors. It seems that all equations include one vertex (or two) of highest degree. In these cases Mixed volume gives (almost) tight bounds.
Approach 1. Find k subgraphs, each with 4 vertices (smallest reasonable size) so that their union contains k unknown distances and also all known distances. Heuristically we should use vertices of highest degree.
People: Ioannis, Guillaume, Michael, Marc, Raimund, Sariel.
13. Raimund Seidel: Maximal Convex subsets
Given a set of points in Rˆd, how many maximal convex subsets are there (i.e. all points are extreme for the subset, and no further points can be added without violating this). A lower bound giving 10ˆ(n/5): put n/5 very large circles tangent to a smaller (?) circle, with 5 points on each. An edge can be chose from each set, and no further points on that curve can be chosen. It also seems like a reverse search scheme can be used to generate them all in polynomial (sub-quadratic?) time per output. The main observation is that if we add one point outside the convex hull of a maximal set, and then greedily add lex-min points until maximal, after a sequence of these "flips", we eventually end up at the convex hull.
People: Raimund, David, Christian, Helmut