^May June – 2010 ^July

Let $X$ be a simple region, and let $Q$ be a set of $m$ points in $X$. A disk cover of $Q$ with respect to $X$, is a set of disks (of variable radii), such that the union of these disks covers $Q$ and is contained in $X$. In other words: (i) each disk in the cover is contained in $X$, and (ii) each point $q in Q$, lies in a disk of the cover. A minimum disk cover of $Q$ with respect to $X$ is a disk cover of $Q$ with respect to $X$ of minimum cardinality. The problem of computing a minimum disk cover of a point set $Q$ with respect to a simple region $X$ arises, e.g., in the following setting. $X$ represents a secured area, and each point of $Q$ represents a client of a radio network. One must place the smallest possible number of transmitters, such that each client is served by at least one of the transmitters (i.e., is within the transmission range of at least one of the transmitters), and any point outside the area, is outside the range of each of the transmitters. Surprisingly, this problem is solvable in polynomial time, due to very nice combinatorial structure. In a paper presented at WADS 2009 and recently accepted to Algorithmica, we presented an exact polynomial time algorithm for the above problem (joint work with Matya Katz). In a paper accepted to ESA 2010 we give an improved almost-linear time algorithm (Joint work with Haim Kaplan, Matya Katz and Micha Sharir). I'll give the highlights of the proof, which I find simple, nice and elegant.

In this talk I will begin with a short background for computer scientists on proteins and their structures. Then I will give a brief overview on some aspects of the challenging field of computational protein structure prediction. In the second part of the talk I will summarize the main project of my PhD thesis: A novel cooperative energy term for hydrogen bonds. (In more details: hydrogen bonds are major constituents of protein structures and thus have been subject to many works. Yet, the common treatment of hydrogen bonds by energy functions is a considerable contributor to the infamous "local minima problem", which has annoyed predictors since the earliest days of this field. Cooperative terms for hydrogen bonds attempt to ease this problem by shifting the focus from the individual hydrogen bond to patterns of hydrogen bonds. I will present the main ideas of our novel cooperative hydrogen-bond term that is both effective and computationally efficient).

We define a simple mathematical problem which we call the optimal base problem: Given a multiset S of positive integers, find a numeral base B such that the size of the representation of S in B is minimal. For example if S={16,30,54,60} then in base 10 the sum of the digits is 25, while in base 2 it is 13, and in base 3 it is 12. The problem gets more interesting when we allow mixed radix bases such as B=<3,5,2,2} with respect to which the sum of the digits in S is only 9. We analyze the complexity of this problem and propose a quasi-polynomial algorithm to solve it. Our implementation improves significantly on existing techniques. Finally we present also an application.

Joint work with Michael Codish, Carsten Fuhs and Peter Schneider-Kamp

The phenomenon of visual curve completion, where the visual system completes the missing contours of an occluded object, is a major problem in computer vision and vision research. I will first present some of the state-of-the-art algorithms for curve completion, as well as relevant perceptual and biological insights. Then I will discuss our own approach for curve completion, which is based on the abstraction of the visual cortex with modern differential geometry tools. In this work we present formal theoretical analysis and numerical solution methods, and we show results on natural images.