Monday, November 14, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We first consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)^{1/2}), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t^{1/2} log n) bound. The result also extends to the more general Komlos setting, where each vector has norm at most 1, and gives an algorithmic O(log^{1/2} n) bound.
Joint work with Nikhil Bansal and Shashwat Garg.
Colloquium - 16:00
Abstract:
Joint work with Bartosz Walczak
We describe the first algorithms to compute the common tangents of two
disjoint simple polygons using linear time and only constant
workspace. A tangent of a polygon is a line touching the polygon such
that all of the polygon lies on the same side of the line. A common
tangent of two polygons is a tangent of both polygons. Each polygon is
given as a read-only array of its corners in cyclic order. We present
very simple algorithms that compute the common tangents when they
exist.
An inner common tangent is a common tangent that separates the
polygons. An outer common tangent is a common tangent such that the
polygons are on the same side of the tangent. We give one algorithm
for the inner common tangents and one for the outer common tangents,
and the algorithms detect when the respective tangents do not exist.
The inner common tangents exist if and only if the convex hulls of the
polygons are disjoint. The outer common tangents exist if and only if
the convex hull of neither polygon is contained in the convex hull of
the other. Thus, our algorithms decide if the convex hulls are nested,
overlapping, or disjoint.