Combinatorial Algorithms Day

Abstract:
Any arrangement of translates of a parabola is combinatorially equivalent to an arrangement of lines. Among others, this observation was used by Pudlák to give an upper bound on incidences in arrangements of parabolas over finite fields and by Valtr who applied it to define a strictly convex norm in R² to obtain many unit distances in a point set. in this talk we are dealing with arrangements of translates of the log curve, log(x+a)+b, and other families of curves having properties similar to the parabola.

Abstract:
The Frechet distance is a distance measure used in shape matching. We give an overview of what is known concerning its computability for polygonal curves and for triangulated surfaces.

Abstract:
In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The player can move vertices, which always keep straight-line connections to their neighbors. The aim is to make the drawing plane as quickly as possible. We investigate the related problem MinMovedVertices which asks for the minimum number of vertex moves. First, we show that MinMovedVertices is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BendPointSetEmbeddability, which yields similar results for that problem. Third, we give bounds for the behavior of MinMovedVertices on several classes of planar graphs, namely cycles, paths, trees, and general planar graphs.

Joint work with Xavier Goaoc, Jan Kratochvil, Chan-Su Shin, and Alexander Wolff

Abstract:
Suppose that we have n objects and want to compare them to detect which pairs of objects are similar. Thus the problem is to output all the pairs of two objects similar to each other in some criteria. Algorithms for this problem has a trivial lower bound on the time complexity; every pair of objects can be similar, thus Θ(n²) time is required for the output process in the worst case. However, in a practical sense, solving such problems is non-sense, and we want to solve the problems with not so many outputs. For the purpose, we want to have an output-sensitive algorithm whose computation time is polynomial, or linear, in the output size N. In this talk, we address a special case of this problem such that each object is a string of fixed length l, and two strings are similar if the hamming distance of the strings is no greater the given threshold d. We will give an algorithm for this problem running in O(_lC_d n N) time, which is optimal if l is a constant. As an application, we show the computation of homology structures (homologs) from large genome sequences.

Abstract:
We study and discuss the relations between problems of the following nature:
1. How many colors suffice for coloring a finite set of balls in the R³ such that every point covered by at least 3 balls, has at least two of its covering balls colored with distinct colors?
2. How many colors suffice for coloring a set of non-intersecting triangles spanned by n points in R³ such that no triangle has all of its 3 vertices colored with the same color?
3. How many colors suffice for coloring a finite set of balls in R³ such that for every covered point there exists a color that is given to at least one but at most two of the covering balls?

Abstract: We introduce a variation on the rules of Avoider-Enforcer positional games. Having done that, we give some motivation behind this variation, illustrating through examples the different behavior of the two sets of rules.

This is joint work with Dan Hefetz, Michael Krivelevich and Tibor Szabó.

Abstract: A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that a magic configuration consists either of points in general position, or all points are collinear, with the possible exception of one point, or they form a special configuration of 7 points.

This is joint work with Eyal Ackerman, Christian Knauer, Rom Pinchasi, and Günter Rote.

Abstract:
Edge casing is a well-known method to improve the readability of drawings of non-planar graphs. A cased drawing orders the edges of each edge crossing and interrupts the lower edge in an appropriate neighborhood of the crossing. Certain orders will lead to a more readable drawing than others. We formulate several optimization criteria that try to capture the concept of a "good" cased drawing. Further, we address the algorithmic question of how to turn a given drawing into an optimal cased drawing. For many of the resulting optimization problems, we either find polynomial time algorithms or NP-hardness results.

Joint work with David Eppstein, Marc van Kreveld, and Elena Mumford.

Abstract:
Given a dense sampling S from the smooth boundary of a planar shape O. We show that the medial axis of the union of Voronoi balls centered at Voronoi vertices inside O has a particularly simple structure and can be computed more efficiently and robustly than for a general union of balls.

Joint work with Balint Miklos and Mark Pauly (both Applied Geometry Group, ETH Zurich)

Abstract:
I will describe a lower bound for the rank of any real matrix in which each diagonal entry is significantly larger than the absolute value of every other entry. This simple result has a surprising number of applications in Geometry, Coding Theory, Extremal Finite Set Theory and the investigation of small sample spaces supporting nearly independent random variables, and I will discuss some of those.