Catálogo de publicaciones - libros

This paper presents an algorithm for rotating a subimage in place without using any extra working array. Due to this constraint, we have to overwrite pixel values by interpolated values. Key ideas are which determines whether interpolation at a pixel is carried out correctly without using interpolated values, and which stores interpolated values in a region which is never used for output images and then fills in interpolated values after safety is guaranteed. It is shown that linear interpolation is always safely implemented. An extension to cubic interpolation is also discussed.

We address the problem of computing critical area for opens in a circuit layout in the presence of multilayer loops and redundant interconnects. The extraction of critical area is a fundamental problem in VLSI yield prediction. We first model the problem as a graph problem and we solve it efficiently by exploiting its geometric nature. We introduce the , a generalization of Voronoi diagrams based on concepts of higher order Voronoi diagrams of segments. Higher order Voronoi diagrams of segments had not received much attention in the literature. The approach expands the Voronoi critical area computation paradigm [1,2,3] with the ability to accurately compute critical area for missing material defects even in the presence of loops and redundant interconnects spanning over multiple layers.

We consider a distributed representation scheme for trees, supporting some special relationships between nodes at small distance. For instance, we show that for a tree and an integer we can assign local information on nodes such that we can decide for any two nodes and if the distance between and is at most and if so, compute it only using the local information assigned. For trees with nodes, the local information assigned by our scheme are binary labels of log + (log(log(/))) bits, improving the results of Alstrup, Bille, and Rauhe (SODA ’03).

We show how to represent sets in a linear space data structure such that expressions involving unions and intersections of sets can be computed in a worst-case efficient way. This problem has applications in e.g. information retrieval and database systems. We mainly consider the RAM model of computation, and sets of machine words, but also state our results in the I/O model. On a RAM with word size , a special case of our result is that the intersection of (preprocessed) sets, containing elements in total, can be computed in expected time ( (log) /  + ), where is the number of elements in the intersection. If the first of the two terms dominates, this is a factor faster than the standard solution of merging sorted lists. We show a cell probe lower bound of time , meaning that our upper bound is nearly optimal for small . Our algorithm uses a novel combination of approximate set representations and word-level parallelism.

We design a faster algorithm for the -maximum sub-array problem under the conventional RAM model, based on distance matrix multiplication (DMM). Specifically we achieve for a general problem where overlapping is allowed for solution arrays. This complexity is sub-cubic when  = (/log). The best known complexities of this problem are ( + log), which is cubic when  = (/log), and , which is sub-cubic when .

Trajectory data is becoming increasingly available and the size of the trajectories is getting larger. In this paper we study the problem of compressing spatio-temporal trajectories such that the most common queries can still be answered approximately after the compression step has taken place. In the process we develop an ( log)-time implementation of the Douglas-Peucker algorithm in the case when the polygonal path of vertices given as input is allowed to self-intersect.

Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. We investigate spatio-temporal movement patterns in large tracking data sets. Specifically we study so-called ‘popular places’, that is, regions that are visited by many entities. We present upper and lower bounds.

We consider two non-convex enclosing shapes with the minimum area; the and the . This paper proposes efficient algorithms computing each of two shapes enclosing a set of points with the minimum area over all orientations. The algorithms run in time quadratic in the number of given points by efficiently maintaining the set of extremal points.

Given a monomial ideal , where are monomials, and a polynomial as an arithmetic circuit the is to test if  ∈ . We show that the problem has a randomized polynomial time algorithm for constant . Furthermore, if is constant and is computed by a circuit with output gate of then we can test whether  ∈  in polynomial time.

This paper shows that it is NP-hard to generate a minimum complete test set for stuck-at faults on the wires of a reversible circuit. We also show non-trivial lower bounds for the size of a minimum complete test set.