Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

A new algorithm for the largest empty rectangle problem

A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).     

Covering a set of points in a plane using two parallel rectangles

In this paper we consider the problem of finding two parallel rectangles in arbitrary orientation for covering a given set of n points in a plane, such that the area of the larger rectangle is minimized. We propose an algorithm that solves the problem in O(n³) time using O(n²) space. Without altering the complexity, our approach can be used to solve another optimization problem namely, minimize the sum of the areas of two arbitrarily oriented parallel rectangles covering a given set of points in a plane.     

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.     

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.     

An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation

The best-fit heuristic by Burke et al. (2004) is a simple but effective approach for the 2D Strip Packing (2DSP) problem. In this paper, we propose an improved best-fit heuristic for the 2DSP. Instead of selecting the rectangle with the largest width, we use the fitness number to select the best rectangle fitting into the gap. An efficient implementation pattern with a time complexity of O(n log n) (n is the number of rectangles) is provided for the improved best-fit heuristic. A simple random local search is used to improve the results by trying different sequences. The experiment on the benchmark test sets shows that the final approach is both effective and efficient.     

A new algorithm for the largest empty rectangle problem

A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).     

A practical divide-and-conquer algorithm for the rectangle intersection problem

We reconsider the problem of finding all pairwise intersections in a set of isooriented rectangles. It has been shown previously that time- and space-optimal solutions for this problem can be obtained using either the line-sweep or the divide-and-conquer paradigm. In this paper we concentrate on some practical aspects of a divide-and-conquer solution. We develop a divide-and-conquer algorithm which solves the problem directly rather than by solving two subproblems, treats special cases elegantly, and has a simple implementation. It has been noted recently that in practical applications the usual assumption that all input data fit into main memory (at the same time) is often unrealistic. This implies that algorithms with sublinear internal space requirements are needed. In the second part of this paper we show that the divide-and-conquer approach supports space-saving techniques very well. If, for instance, any vertical cross section through the set of n rectangles intersects at most c rectangles [in practice this often holds for c = O(√n)], then our algorithm can easily be modified to run in O(c) internal space and still optimal time. Another modification permits to run the algorithm completely or partly externally. That is, the internal space requirements can be selected to be O(m), for 1 ⩽ m ⩽ n, without increasing the asymptotic time complexity or requiring “too many” disk accesses. This means that the problem can be solved efficiently even on a very small computer.     

形状角计算改进及其在矩形目标识别中的应用

目的 在轮廓特征识别中,形状角理论已经被证明为一种有效方法.形状角的计算精度和时间开销取决于轮廓上各离散点处切线方向的计算效率.现有基于Vialard算法的切线方向计算方法在处理矩形轮廓时步骤烦琐且存在较大的误差,导致使用形状角识别矩形时效率不高.针对此问题,提出一种基于傅里叶拟合的离散点切线方向计算方法.方法 首先对离散点进行极坐标转化,然后使用傅里叶级数拟合整个轮廓,最后再对拟合之后的曲线求导,从而计算出轮廓上各点的切线方向.结果 在本文所给出的实例中,本文方法计算平均耗时为1.5775 s,传统方法平均耗时为156.155 s,且计算结果更加精确.结论 本文方法可以避免Vialard算法及其衍生方法在处理矩形轮廓时产生的过度迭代的问题,时间复杂度降低两个数量级,结果更加准确.最后,将所提的改进形状角计算方法应用矩形轮廓识别中,通过实例分析,验证了该方法的准确性和可靠性.     

An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules

We address an important variant of the rectangle packing problem, the soft rectangle packing problem, and explore its problem extension for the fixed-outline floorplanning with soft modules. For the soft rectangle packing problem with zero deadspace, we present an iterative merging packing algorithm that merges all the rectangles into a final composite rectangle in a bottom-up order by iteratively merging two rectangles with the least areas into a composite rectangle, and then shapes and places each pair of sibling rectangles based on the dimensions and position of their composite rectangle in an up-bottom order. We prove that the proposed algorithm can guarantee feasible layout under some conditions, which are weaker as compared with a well-known zero-dead-space packing algorithm. We then provide a deadspace distribution strategy, which can systematically assign deadspace to modules, to extend the iterative merging packing algorithm to deal with soft packing problem with deadspace. For the fixed-outline floorplanning with soft modules problem, we propose an iterative merging packing based hierarchical partitioning algorithm, which adopts a general hierarchical partitioning framework as proposed in the popular PATOMA floorplanner. The framework uses a recursive bipartitioning method to partition the original problem into a set of subproblems, where each subproblem is a soft rectangle packing problem and how to solve the subproblem plays a key role in the final efficiency of the floorplanner. Different from the PATOMA that adopts the zero-dead-space packing algorithm, we adopt our proposed iterative merging packing algorithm for the subproblems. Experiments on the IBM-HB benchmarks show that the proposed packing algorithm is more effective than the zero-dead-space packing algorithm, and experiments on the GSRC benchmarks show that our floorplanning algorithm outperforms three state-of-the-art floorplanners PATOMA, DeFer and UFO, reducing wirelength by 0.2%, 4.0% and 2.3%, respectively.     

Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

Efficient tile sets for self assembling rectilinear shapes is of critical importance in algorithmic self assembly. A lower bound on the tile complexity of any deterministic self assembly system for an n?×?n square is $\Upomega(\frac{\log(n)}{\log(\log(n))})$ (inferred from the Kolmogrov complexity). Deterministic self assembly systems with an optimal tile complexity have been designed for squares and related shapes in the past. However designing $\Uptheta(\frac{\log(n)}{\log(\log(n))})$ unique tiles specific to a shape is still an intensive task in the laboratory. On the other hand copies of a tile can be made rapidly using PCR (polymerase chain reaction) experiments. This led to the study of self assembly on tile concentration programming models. We present two major results in this paper on the concentration programming model. First we show how to self assemble rectangles with a fixed aspect ratio (??:??), with high probability, using $\Uptheta(\alpha+\beta)$ tiles. This result is much stronger than the existing results by Kao et?al. (Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) and Doty (Randomized self-assembly for exact shapes. In: proceedings of the 50th annual IEEE symposium on foundations of computer science (FOCS), IEEE, Atlanta. pp 85?C94, 2009)??which can only self assembly squares and rely on tiles which perform binary arithmetic. On the other hand, our result is based on a technique called staircase sampling. This technique eliminates the need for sub-tiles which perform binary arithmetic, reduces the constant in the asymptotic bound, and eliminates the need for approximate frames (Kao et?al. Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) . Our second result applies staircase sampling on the equimolar concentration programming model (The tile complexity of linear assemblies. In: proceedings of the 36th international colloquium automata, languages and programming: Part I on ICALP ??09, Springer-Verlag, pp 235?C253, 2009), to self assemble rectangles (of fixed aspect ratio) with high probability. The tile complexity of our algorithm is $\Uptheta(\log(n))$ and is optimal on the probabilistic tile assembly model (PTAM)??n being an upper bound on the dimensions of a rectangle.     

An approximation algorithm for sequential rectangle placement

We present a constant factor, polynomial time approximation algorithm for the problem of scheduling a sequence of rectangles on a matrix. The approximation is on the area covered by the rectangles, and a rectangle is placed on the matrix only if all its preceding rectangles in the sequence were already placed.     

Finding best-fitted rectangle for regions using a bisection method

In this paper, we have presented a new method for computing the best-fitted rectangle for closed regions using their boundary points. The vertices of the best-fitted rectangle are computed using a bisection method starting with the upper-estimated rectangle and the under-estimated rectangle. The vertices of the upper- and under-estimated rectangles are directly computed using closed-form solutions by solving for pairs of straight lines. Starting with these two rectangles, we solve for the best-fitted rectangle iteratively using a bisection method. The algorithm stops when the areas of the fitted rectangles remain unchanged during consecutive iterations. Extensive evaluation of our algorithm demonstrates its effectiveness.     

A new fast heuristic for labeling points

In the point site labeling problem, we are given a set P={p₁,p₂,…,pn} of point sites in the plane. The label of a point pi is an axis-parallel rectangle of specified size. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. Here, we investigate a special class of the point site labeling problem where (i) height of the labels of all the points are same but their lengths may differ, (ii) the label of a point pi touches the point at one of its four corners, and (iii) the label of one point does not obscure any other point in P. We describe an efficient heuristic algorithm for this problem which runs in time in the worst case. We run our algorithm as well as the algorithm Rules proposed by Wagner et al. on randomly generated point sets and on the available benchmarks. The results produced by our algorithm are almost the same as Rules in most of the cases. But our algorithm is faster than Rules in dense instance. We have also computed the optimum solutions for all the examples we have considered by designing an algorithm, which performs an exhaustive search in the worst case. We found that the exhaustive search algorithm runs reasonably fast for most of the examples we have considered.     

Characterizing the shapes of noisy,non-uniform,and disconnected point clusters in the plane

Many spatial analyses involve constructing possibly non-convex polygons, also called “footprints,” that characterize the shape of a set of points in the plane. In cases where the point set contains pronounced clusters and outliers, footprints consisting of disconnected shapes and excluding outliers are desirable. This paper develops and tests a new algorithm for generating such possibly disconnected shapes from clustered points with outliers. The algorithm is called χ-outline, and is based on an extension of the established χ-shape algorithm. The χ-outline algorithm is simple, flexible, and as efficient as the most widely used alternatives, O(n log n) time complexity. Compared with other footprint algorithms, the χ-outline algorithm requires fewer parameters than two-step clustering-footprint generation and is not limited to simple connected polygons, a limitation of χ-shapes. Further, experimental comparison with leading alternatives demonstrates that χ-outlines match or exceed the accuracy of α-shapes or two-step clustering-footprint generation, and is more robust to some forms of non-uniform point densities. The effectiveness of the algorithm is demonstrated through the case study of recovering the complex and disconnected boundary of a wildfire from crowdsourced wildfire reports.     

An efficient algorithm for maxdominance,with applications

Given a planar setS ofn points,maxdominance problems consist of computing, for everyp εS, some function of the maxima of the subset ofS that is dominated byp. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle. We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.     

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/?_crit + 1)n(logn)²), wherea ≥b are the lengths of the sides of a rectangle and ?_crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.     

Polychromatic 4-coloring of guillotine subdivisions

A polychromatic k-coloring of a plane graph G is an assignment of k colors to the vertices of G such that each face of G, except possibly for the outer face, has all k colors on its boundary. A rectangular partition is a partition of a rectangle R into a set of non-overlapping rectangles such that no four rectangles meet at a point. It was conjectured in [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: 23rd European Workshop Computational Geometry, 2007, pp. 30-33] that every rectangular partition admits a polychromatic 4-coloring. In this note we prove the conjecture for guillotine subdivisions — a well-studied subfamily of rectangular partitions.     

Constant Approximation Algorithms for Rectangle Stabbing and Related Problems

In this paper we present constant approximation algorithms for two NP-hard rectangle stabbing problems, called the weighted rectangle stabbing (WRS) problem and the rectangle stabbing with rejecting cost (RSRC) problem. In the WRS problem a set of axis-aligned rectangles is given, with each rectangle associated with a positive weight, and a set of weighted horizontal and/or vertical stabbing lines is sought so that each rectangle is intersected by at least one stabbing line with a weight (called cost) no less than that of the rectangle and the total cost (or weight) of all stabbing lines is minimized. In the RSRC problem each rectangle is associated with an additional positive rejecting cost and is required to be either stabbed by a stabbing line or rejected by paying its rejecting cost. For the WRS problem, we present a polynomial time 2e-approximation algorithm, where e is the natural logarithmic base. Our algorithm is based on a number of interesting techniques such as rounding, randomization, and lower bounding. For the RSRC problem, we give a 3e-approximation algorithm by using a simple but powerful LP rounding technique to identify those to-be-rejected rectangles. Our techniques are quite general and can be easily applied to several related problems, such as the stochastic rectangle stabbing problem and polygon stabbing problem from fixed directions. Algorithms obtained by our techniques are relatively simple and can be easily implemented for practical purpose.     

An in-place algorithm for Klee's measure problem in two dimensions

We present the first in-place algorithm for solving Klee's measure problem for a set of n axis-parallel rectangles in the plane. Our algorithm runs in O(n3/2logn) time and uses O(1) extra words in addition to the space needed for representing the input. The algorithm is surprisingly simple and thus very likely to yield an implementation that could be of practical interest. As a byproduct, we develop an optimal algorithm for solving Klee's measure problem for a set of n intervals; this algorithm runs in optimal time O(nlogn) and uses O(1) extra space.