Michiel Smid - University of Magdeburg

Translating a planar object to maximize point containment: Exact and approximation algorithms

Abstract: Let C be a closed and bounded set in the plane and let S be a set of n points in the plane. We consider the problem of computing a translate of C that contains the maximum number of points of S. We start by giving two basic algorithms for this problem whose running times are roughly quadratic in n. Then we show how random sampling can be used to transform any deterministic algorithm for this optimal-placement problem into a Monte Carlo approximation algorithm. For sets C that satisfy a certain fatness condition, we use a simple bucketing technique to transform any algorithm for the optimal-placement problem into an algorithm that solves the same problem. The bucketing transformation can be implemented in the algebraic computation-tree model, or in a more powerful model using hashing. Applying the random-sampling and bucketing transformations to the two basic algorithms, we obtain a variety of results. For example, if C is a convex polygon with m vertices, we can solve the optimal-placement problem in the algebraic computation-tree model in O(n \log n + mn \log (m k*) + n k*) time, where k* is the number of points in an optimal placement of C. Also, for any constants epsilon,c>0, we can compute a placement of C that contains at least (1 - epsilon) k* points in O(m + n \log (mn)) time with error probability at most e^{-c \sqrt{k*}}. Employing hashing techniques, we can implement this algorithm so that its running time is bounded by O(m + n \log m).
(This is joint work with Torben Hagerup and Rahul Ray.)

Colloquium - 16:00

Ileana Streinu - Northhampton, MA

Pseudo-Triangulations, Rigidity Theory and Efficiently Planning Non-Colliding Robot Arm Motions

Abstract: Is it always possible to convexify a simple planar polygon with a continuous motion that rotates the fixed-length edges around the vertices, stays in the plane and avoids self-intersections? If so, then one can move continuously from any configuration of a simple fixed-edge-length polygon (or planar robot arm) to any other and maintain simplicity throughout. A positive answer to this long standing open question was given recently by Connelly, Demaine and Rote. In this talk I describe an extension of this result to an effective, efficient and surprisingly simple combinatorial approach for planning the motion. It is based on a novel class of embedded minimally rigid planar graphs called pseudo triangulations, which possess rich combinatorial properties and can be characterized in many equivalent ways. I will discuss the rigidity-theoretical properties of pseudo triangulations and several algorithms for constructing and using them in the convexifying motion.