In this paper, we introduce the notion of a constrained Minkowski sumwhich for two (finite) point-sets P,Q⊆ R2 and a set of k inequalities Ax≥ b is defined as the point-set (P ⊕ Q)Ax≥ b= x = p+q | ∈ P, q ∈ Q, , Ax ≥ b. We show that typical subsequenceproblems from computational biology can be solved by computing a setcontaining the vertices of the convex hull of an appropriatelyconstrained Minkowski sum. We provide an algorithm for computing such a setwith running time O(N log N), where N=|P|+|Q| if k is fixed. For the special case (P⊕ Q)x1≥ β, where P and Q consistof points with integer x1-coordinates whose absolute values arebounded by O(N), we even achieve a linear running time O(N). Wethereby obtain a linear running time for many subsequence problemsfrom the literature and improve upon the best known running times forsome of them.The main advantage of the presented approach is that it provides a generalframework within which a broad variety of subsequence problems canbe modeled and solved.This includes objective functions and constraintswhich are even more complexthan the ones considered before.

Heilbronn conjectured that given arbitrary n points from the 2-dimensional unit square, there must be three points which form a triangle of area at most O(1/n 2 ). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz, and Szemerédi [ J. London Math. Soc., 25 (1982), pp. 13--24] who showed that for every n there is a configuration of n points in the unit square where all triangles have area at least $\Omega({\log n}/{n^2})$. Considering a discretization of Heilbronn's problem, we give an alternative proof of the result from [J. London Math. Soc., 25 (1982), pp. 13--24]. Our approach has two advantages: First, it yields a polynomial-time algorithm which for every n computes a configuration of n points where all triangles have area $\Omega({\log n}/{n^2})$. Second, it allows us to consider a generalization of Heilbronn's problem to convex hulls of k points where we can show that an algorithmic solution is also available.

An artificial neural network (ANN) is commonly modeled by a threshold circuit, a network of interconnected processing units called linear threshold gates. It is shown that ANNs can be much more powerful than traditional logic circuits, assuming that each threshold gate can be built with a cost that is comparable to that of AND/OR logic gates. In particular, the main results indicate that powering and division can be computed by polynomial-size ANNs of depth 4, and multiple product can be computed by polynomial-size ANNs of depth 5. Moreover, using the techniques developed, a previous result can be improved by showing that the sorting of n n-bit numbers can be carried out in a depth-3 polynomial-size ANN. Furthermore, it is shown that the sorting network is optimal in depth.>