Approximation Algorithms for Aligning Points

We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own given region. Different shapes of placement regions and different sets of alignment orientations are considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide an inapproximability result for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends on the shape of the given regions and the set of orientations. When the orientations are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.     

Optimal algorithms for rectangle problems on a mesh-connected computer

In this paper, Mesh-Connected Computer (MCC) algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, we describe MCC algorithms for determining the following properties: (i) the area of the logic “OR” of these rectangles (i.e., the area of the region covered by at least one rectangle); (ii) the area of the union of pairwise “AND” of the rectangles (i.e., the area of the region covered by two or more rectangles); (iii) the largest number of rectangles that overlap (this solves the fixed-size rectangle placement problem, i.e., given a set of planar points and a rectangle, find a placement of the rectangle in the plane so that the number of points covered by the rectangle is maximal); (iv) the minimum separation between any pair of a set of nonoverlapping rectangles. All these algorithms can be implemented on a 2√n × 2√n MCC in O(√n) time which is optimal. The algorithms compare favorably with the known sequential algorithms that have O(n log n) time complexity.     

Recovering shape and motion by a dynamic system for low-rank matrix approximation in L 1 norm

To recover motion and shape matrices from a matrix of tracking feature points on a rigid object under orthography, we can do low-rank matrix approximation of the tracking matrix with its each column minus the row mean vector of the matrix. To obtain the row mean vector, usually 4-rank matrix approximation is used to recover the missing entries. Then, 3-rank matrix approximation is used to recover the shape and motion. Obviously, the procedure is not convenient. In this paper, we build a cost function which calculates the shape matrix, motion matrix as well as the row mean vector at the same time. The function is in L ₁ norm, and is not smooth everywhere. To optimize the function, a continuous-time dynamic system is newly proposed. With time going on, the product of the shape and rotation matrices becomes closer and closer, in L ₁-norm sense, to the tracking matrix with each its column minus the mean vector. A parameter is implanted into the system for improving the calculating efficiency, and the influence of the parameter on approximation accuracy and computational efficiency are theoretically studied and experimentally confirmed. The experimental results on a large number of synthetic data and a real application of structure from motion demonstrate the effectiveness and efficiency of the proposed method. The proposed system is also applicable to general low-rank matrix approximation in L ₁ norm, and this is also experimentally demonstrated.     

Parallel computational geometry of rectangles

Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).     

Digital approximation of continuous-data control systems by point-by-point state comparison

This paper presents a point-by-point state comparison method of approximating a continuous-data system by a sampled-data system. The problem is to attempt the matching of the states of the two systems at the sampling instants. A partial matching has to be conducted if the systems have more states than controls. A weighting matrix is used to regulate the partial matching and weights placed on each state.The digital approximation is affected by use of forward gain E(T) and feedback gain G(T) in the sampled-data system. It is shown that, in general, these gains can be approximated by truncated Taylor series expansions.An illustrative example is given using the one-axis dynamics of the Skylab satellite.     

Low-rank matrix decomposition in L1-norm by dynamic systems

Low-rank matrix approximation is used in many applications of computer vision, and is frequently implemented by singular value decomposition under L₂-norm sense. To resist outliers and handle matrix with missing entries, a few methods have been proposed for low-rank matrix approximation in L₁ norm. However, the methods suffer from computational efficiency or optimization capability. Thus, in this paper we propose a solution using dynamic system to perform low-rank approximation under L₁-norm sense. From the state vector of the system, two low-rank matrices are distilled, and the product of the two low-rank matrices approximates to the given measurement matrix with missing entries, in L₁ norm. With the evolution of the system, the approximation accuracy improves step by step. The system involves a parameter, whose influences on the computational time and the final optimized two low-rank matrices are theoretically studied and experimentally valuated. The efficiency and approximation accuracy of the proposed algorithm are demonstrated by a large number of numerical tests on synthetic data and by two real datasets. Compared with state-of-the-art algorithms, the newly proposed one is competitive.     

Cache-Oblivious R-Trees

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant ε, a structure that answers a rectangle query using \(O(\sqrt{N/B}+T/B)\) memory transfers and a point query using O((N/B) ^ε ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.     

Online multiple-strip packing

We study an online multiple-strip packing problem, whose goal is to pack the given rectangles into m vertical strips of unit width such that the maximum height used among the strips is minimized. Rectangles arrive one by one. The decision of delivering the rectangles to a strip as well as packing them into the strip must be done immediately and irrevocably without any information on the next rectangles. Both randomized and deterministic online algorithms are investigated, all of which are guaranteed a constant competitive ratio.     

The Parameterized Complexity of Stabbing Rectangles

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)?|R∪L| ^O(1) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that “almost have the consecutive-ones property”, that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) ^k ?|R∪L| ^O(1) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rectangles have bounded width or height or where each horizontal line intersects only a bounded number of rectangles.     

Reasoning with geometric information in digital space

Concurrency requires consistency and correctness. Isothetic rectangles can be used as a geometrical technique to verify a safe and deadlock free schedule for concurrent nodes. However, the known algorithms for concurrency using isothetic rectangles require the prior knowledge of the system behavior. We provide a new mechanism to use isothetic rectangles without this limitation. The discrete nature of isothetic rectangles provides an opportunity for inter-diagrammatic reasoning. Inter-Diagrammatic Reasoning (IDR) can be easily computed on a parallel machine, and has a complexity of O(n) for most of the iso-rectangles problems where the best known algorithm was O(n log n) in Euclidean geometry. This new framework will also allow dynamic mode of operation in calculating the closure of a set of iso-rectangles; rather than restricting the solution to static systems where all required resources must be reserved in advance.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

The matrix ridge approximation: algorithms and applications

We are concerned with an approximation problem for a symmetric positive semidefinite matrix due to motivation from a class of nonlinear machine learning methods. We discuss an approximation approach that we call matrix ridge approximation. In particular, we define the matrix ridge approximation as an incomplete matrix factorization plus a ridge term. Moreover, we present probabilistic interpretations using a normal latent variable model and a Wishart model for this approximation approach. The idea behind the latent variable model in turn leads us to an efficient EM iterative method for handling the matrix ridge approximation problem. Finally, we illustrate the applications of the approximation approach in multivariate data analysis. Empirical studies in spectral clustering and Gaussian process regression show that the matrix ridge approximation with the EM iteration is potentially useful.     

Approximation algorithms for partitioning a rectangle with interior points

LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a valid partition must not contain points fromP as interior points. Since this partitioning problem is computationally intractable (NP-hard), we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within three times the optimal solution value. Our algorithm also generates solutions within four times the optimal solution value whenR is a rectilinear polygon. Our algorithm can be generalized to generate good approximation solutions for the case whenR is a rectilinear polygon, there are rectilinear polygonal holes, and the sum of the length of the boundaries is not more than the sum of the length of the edges in an optimal solution.     

A quasi-Newton method with Cholesky factorization

A quasi-Newton method for unconstrained minimization is presented, which uses a Cholesky factorization of an approximation to the Hessian matrix. In each step a new row and column of this approximation matrix is determined and its Cholesky factorization is updated. This reduces storage requirements and simplifies the calculation of the search direction. Precautions are taken to hold the approximation matrix positive definite. It is shown that under usual conditions the method converges superlinearly or evenn-step quadratic.     

Packing rectangles in a strip

Rectangles with dimensions independently chosen from a uniform distribution on [0,1] are packed on-line into a unit-width strip under a constraint like that of the Tetris game: rectangles arrive from the top and must be moved inside the strip to reach their place; once placed, they cannot be moved again. Cargo loading applications impose similar constraints. This paper assumes that rectangles must be moved without rotation. For n rectangles, the resulting packing height is shown to have an asymptotic expected value of at least (0.31382733 ...)n under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of (0.36976421 ...)n. This algorithm improves the bound achieved in Next Fit Level (NFL) packing, by compressing the items packed on two successive levels of an NFL packing via on-line movement admissible under the Tetris constraint. Received: 6 February 2001 / 25 June 2002     

Computing a consistent approximation to a generalized pairwise comparisons matrix

This paper presents an algorithm for computing a consistent approximation to a generalized pairwise comparisons matrix (that is, without the reciprocity property or even 1s on the main diagonal). The algorithm is based on a logarithmic transformation of the generalized pairwise comparisons matrix into a linear space with the Euclidean metric. It uses both the row and (reciprocals of) column geometric means and is thus a generalization of the ordinary geometric means method. The resulting approximation is not only consistent, but also closest to the original matrix, i.e., deviates least from an expert's original judgments. The computational complexity of the algorithm is O(n²).     

Identifying rectangles in laser range data for urban scene reconstruction

In urban scenes, many of the surfaces are planar and bounded by simple shapes. In a laser scan of such a scene, these simple shapes can still be identified. We present a one-parameter algorithm that can identify point sets on a plane for which a rectangle is a fitting boundary. These rectangles have a guaranteed density: no large part of the rectangle is empty of points. We prove that our algorithm identifies all angles for which a rectangle fits the point set of size n in O(nlogn) time. We evaluate our method experimentally on 13 urban data sets and we compare the rectangles found by our algorithm to the α‐shape as a surface boundary.     

Hierarchical data visualization using a fast rectangle-packing algorithm

This paper presents a technique for the representation of large-scale hierarchical data which aims to provide good overviews of complete structures and the content of the data in one display space. The technique represents the data by using nested rectangles. It first packs icons or thumbnails of the lowest-level data and then generates rectangular borders that enclose the packed data. It repeats the process of generating rectangles that enclose the lower-level rectangles until the highest-level rectangles are packed. This paper presents two rectangle-packing algorithms for placing items of hierarchical data onto display spaces. The algorithms refer to Delaunay triangular meshes connecting the centers of rectangles to find gaps where rectangles can be placed. The first algorithm places rectangles where they do not overlap each other and where the extension of the layout area is minimal. The second algorithm places rectangles by referring to templates describing the ideal positions for nodes of input data. It places rectangles where they do not overlap each other and where the combination of the layout area and the distances between the positions described in the template and the actual positions is minimal. It can smoothly represent time-varying data by referring to templates that describe previous layout results. It is also suitable for semantics-based or design-based data layout by generating templates according to the semantics or design.     

An exact strip packing algorithm based on canonical forms

Given a set of rectangles and a rectangular container with a fixed width, called a strip, the two-dimensional strip packing problem (2SP) requires all the given rectangles to be placed orthogonally without overlap within the strip so as to minimize the height of the strip. 2SP and its variants have many applications in steel and textile industries, including an indirect application in scheduling problems. However, 2SP is known to be NP-hard.     

Optimizing regenerator cost in traffic grooming

In optical networks, regenerators have to be placed on lightpaths every d consecutive nodes in order to regenerate the signal. In addition, grooming enables the use of the same regenerator by several lightpaths. Up to g (the grooming factor) lightpaths can use the same regenerator. In this work we consider the problem of minimizing the number of regenerators used in traffic grooming in optical networks. Starting from the 4-approximation algorithm of Flammini et al. (2010) [10] for d=1 and a path topology, we provide an approximation algorithm with the same approximation ratio for d=1and the ring and tree topologies. We present also a technique based on matching that leads to the same approximation ratio in tree topology and can be used to obtain approximation algorithms in other topologies. We provide an approximation algorithm for general topology that uses this technique. Finally, all the results are extended to the case of general d.