Search

The length-constrained heaviest path (LCHP) in a weighted tree T, where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(nlogn) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al. (1999), which runs in O(nlog^2n) time. Our method also improves on a previous O(nlogn) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.

In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like the Marr-Poggio algorithm, this means that we study how to solve the unrestricted basic subproblems created within such approaches, possibly yielding an improved overall performance of such methods. We present an O(n2 + 4k) time and O(n4) space algorithm for exact unrestricted stereo matching, where n represents the number of points in each set and k the number of depth levels considered. We generalize the notion of a δ-approximate solution for point set congruence to the stereo matching problem and present an O (( e δ ) k n 2 + 2k ) time and O (( e δ )n 2 ) space δ-approximate algorithm for unrestricted stereo matching (e represents measurement inaccuracies in the image). We introduce new computational geometry tools for stereo matching: the translation square arrangement, approximate translation square arrangement and approximate stereo matching tree.

Consider a set S of n points in the Euclidean plane. We obtain efficient parallel algorithms for the following two problems: (i) compute the contour spanned by the maximal elements of S, and (ii) compute the number of dominated points for every element of S (ECDF searching problem). Both algorithms run in O(n 1 2 ) time on a mesh of n processors, which is asymptotically optimal since any nontrivial computation requires Ω( n 1 2 ) time on the mesh. The algorithms can be generalized to solved the d-dimensional maximal elements and ECDF searching problem in O(n 1 2 + log 2 ( d −2) )( d > 2) time.

Dehne (1986) presented an optimal O(√ n ) time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a mesh-of-processors of size n . However, it remained an open problem whether such an optimal solution exists for the d -dimensional ECDF searching problem for d ⩾4. In this paper we solve this problem by presenting an optimal O(√ n ) time parallel solution to the d -dimensional ECDF searching problem for arbitrary dimension d = O(1) on a mesh-of-processors of size n . The algorithm has several interesting implications. Among others, the following problems can now be solved on a mesh-of-processors in (asymptotically optimal) time O(√ n ) for arbitrary dimension d = O(1): the d -dimensional maximal element determination problem, the d -dimensional hypercube containment counting problem, and the d -dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2 d -dimensional ECDF searching problem but require an efficient solution to this problem for at least d ⩾4.