A simple method for fitting of bounding rectangle to closed regions

In this paper, we introduce a new approach for fitting of a bounding rectangle to closed regions. In this approach the coordinates of the vertices are computed directly using a closed-form solution. This approach is based on simple coordinate geometry and uses the boundary points of regions. Using a least-square approach we determine the directions of major and minor axes of the object, which gives the orientation of the object. The four vertexes of the bounding rectangle are computed by pair wise solving the four straight lines. Examples from synthetic data and some real-life data show that the approach is both accurate and efficient.     

Finding a small number of regions in an image using low-level features

Many computer vision applications, such as object recognition, active vision, and content-based image retrieval (CBIR) could be made both more efficient and effective if the objects of most interest could be segmented easily from the background. In this paper, we discuss how to compute and process low-level features in order to obtain “reasonable” regions for the putative objects. This process is a precursor to the detection of salient objects in an image, a subject discussed in a companion report [1]. Although considerable work has been done on image segmentation, there still does not exist an “off-the-shelf” solution applicable to all types of images. A major issue has been the lack of a good measure of quality of a particular segmentation. In this paper, three different measures are considered: the non-parametric measure (NP) proposed by Pauwels and Frederix [2], the modified Hubert index (MH) [3], and a threshold-based measure with a manually selected threshold. From the experimental results, we have found that the simple threshold-based measure gave consistently better results than the other two more complex, statistically based measures. The particular image segmentation method we have employed in this study is also described in detail.     

Complexity of the bisection method

The bisection method   is the consecutive bisection of a triangle by the median of the longest side. In this paper we prove a subexponential asymptotic upper bound for the number of similarity classes of triangles generated on a mesh obtained by iterative bisection, which previously was known only to be finite. The relevant parameter is γ/σ$\gamma /\sigma$, where γ$\gamma$ is the biggest and σ$\sigma$ is the smallest angle of the triangle. We get this result by introducing a taxonomy of triangles that precisely captures the behaviour of the bisection method. We also prove that the number of directions on the plane given by the sides of the triangles generated is finite. Additionally, we give purely geometrical and intuitive proofs of classical results for the bisection method.     

基于两分法的全局最优化方法

结合分形的思想方法将经典的两分法推广到平面上,提出了一种求解非线性优化问题全局最优值的新算法。该方法稳定精确、简单易行,有效地克服了传统方法易于陷入局部最优的弊端。算法的收敛性得到证明,算例表明算法是有效的。     

Semi-inverse method for a plane strain gradient orthotropic elastic rectangle in tension

Microsystem Technologies - Considering a simple form of the strain energy functional for anisotropic elastic materials as proposed with Lazar and Kirchner (Int J Solids Struct...     

An interactive rectangle elimination method for biobjective decision making

This paper presents a new man-machine interactive method for biobjective decision making. It is specifically designed to cope with both the ill-defined nature of the decision problem and the high cost of computation points in the tradeoff (Pareto optimal) set. With this method, the decision maker may efficiently approximate the tradeoff set and/or estimate his preferred objective value. First, the notion of a rectangle representation of the tradeoff set by a set of points, called experiments, and a set of rectangles, defined by the experiments, is introduced. Next, a special class of decision makers is considered. For a decision maker in this special class, the rectangle representation of the tradeoff set defines a rectangle of uncertainty that contains the decision maker's preferred objective value. A measure of the worst ease uncertainity is formulated and minimized to yield an optimal strategy for interactively selecting experiments. Finally, this strategy is employed in a general interactive algorithm that works under minimal assumptions on the tradeoff set and on the decision maker.     

Parallel decoupled terminal-edge bisection method for 3D mesh generation

We present a practical and stable algorithm for the parallel refinement of tetrahedral meshes. The algorithm is based on the refinement of terminal-edges and associated terminal stars. A terminal-edge is a special edge in the mesh which is the longest edge of every element that shares such an edge, while the elements that share a terminal-edge form a terminal star. We prove that the algorithm is inherently decoupled and thus scalable. Our experimental data show that we have a stable implementation able to deal with hundreds of millions of tetrahedra and whose speed is in between one and two order of magnitude higher from the method and implementation we presented (Rivara et al., Proceedings 13th international meshing roundtable, 2004).Maria-Cecilia Rivara and Carlo Calderon's work was partially supported by Fondecyt 1040713.Andriy Fedorov’s work is supported in part by ITR #ACI-0085969, and NGS #ANI-0203974.Nikos Chrisochoides’s work is supported in part by NSF Career Award #CCR-0049086, ITR #ACI-0085969, NGS #ANI-0203974, and ITR #CNS-0312980.     

Covolume method for new nonconforming rectangle element for the Stokes problem

We analyze a covolume method based on the new nonconforming element introduced by Douglas et al. [1]. We show the H¹ optimal order convergence of the scheme for Stokes problem and study the hybrid domain decomposition procedure for this covolume scheme. The numerical experiment shows that the covolume scheme is somewhat better than finite element scheme in the computation of pressure.     

Solving the minimum bisection problem using a biologically inspired computational model

The traditional trend of DNA computing aims at solving computationally intractable problems. The minimum bisection problem (MBP) is a well-known NP-hard problem, which is intended to partition the vertices of a given graph into two equal halves so as to minimize the number of those edges with exactly one end in each half. Based on a biologically inspired computational model, this paper describes a novel algorithm for the minimum bisection problem, which requires a time cost and a DNA strand length that are linearly proportional to the instance size.     

On a construction of a hierarchy of best linear splineapproximations using repeated bisection

We present a method for the construction of hierarchies of single-valued functions in one, two, and three variables. The input to our method is a coarse decomposition of the compact domain of a function in the form of an interval (univariate case), triangles (bivariate case), or tetrahedra (trivariate case). We compute best linear spline approximations, understood in an integral least squares sense, for functions defined over such triangulations and refine triangulations using repeated bisection. This requires the identification of the interval (triangle, tetrahedron) with largest error and splitting it into two intervals (triangles, tetrahedra). Each bisection step requires the recomputation of all spline coefficients due to the global nature of the best approximation problem. Nevertheless, this can be done efficiently by bisecting multiple intervals (triangles, tetrahedra) in one step and by reducing the bandwidths of the matrices resulting from the normal equations     

基于两阶段排放算法的矩形件排样优化方法

针对矩形件排样问题,经典的最下左填充(BLF)算法易于出现区域浪费、原材料利用率低的缺点。对此,提出一种改进的两阶段排放算法。第一阶段利用BLF算法,第二阶段设计一个改进BLF排放算法以减小区域的浪费。再以矩形件排放顺序进行编码,利用两阶段排放算法解码,设计邻域搜索算法寻找最优解。通过已有文献的多个案例,对改进的算法进行实验验证,结果与BLF算法相比,原材料利用率能提高14%,证实了改进算法的有效性。     

Control of three-link underactuated manipulators using a switching method of fuzzy energy regions

In general, manipulators used for industry and in academic laboratories have actuators to drive each joint. On the other hand, underactuated manipulators handled by our research have some passive or free joints without actuators and brakes. We recently developed a switching method of fuzzy energy regions to control such manipulators. In such a method, it is necessary to design parameters related to energy regions and the gains of some partly stable controllers based on the computed torque method. Here, the switching method is applied for a three-link underactuated manipulator. We optimize such design parameters related to fuzzy energy regions by a genetic algorithm. The effectiveness of the present method is illustrated with some simulations. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

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 preliminary version of this paper appeared in theProceedings of the Symposium on Computational Geometry, June 1985, pp. 281–287. This research was supported in part by the National Science Foundation under Grant DCR-8503163.     

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.     

Implementation of the bisection sampling method in path integral simulations

A bisection sampling method is implemented in the framework of a quantized classical path algorithm to include nuclear quantum effects in path integral simulations. The present study examines the convergence of these calculations on two model systems with respect to the number of beads used in the polymer chain and the number of configurations both in free-particle sampling and in classical configuration sampling. The results will be useful for future studies of kinetic isotope effects in enzymatic reactions.     

Finding an optimal partition for a numerical integration using the trapezoidal rule

When a method of numerical integration is implemented on a computer, it is performed with a limited precision arithmetic. This causes a computing error propagated at the level of each elementary operation and affecting, like the method error, the final computed result.The global error depends on the integrating step.In this paper, we present a new method for estimating these errors and for evaluating the optimum integrating step for which the global error is minimum.     

Finding map regions with high density of query keywords

We consider the problem of finding map regions that best match query keywords. This region search problem can be applied in many practical scenarios such as shopping recommendation, searching for tourist attractions, and collision region detection for wireless sensor networks. While conventional map search retrieves isolate locations in a map, users frequently attempt to find regions of interest instead, e.g., detecting regions having too many wireless sensors to avoid collision, or finding shopping areas featuring various merchandise or tourist attractions of different styles. Finding regions of interest in a map is a non-trivial problem and retrieving regions of arbitrary shapes poses particular challenges. In this paper, we present a novel region search algorithm, dense region search (DRS), and its extensions, to find regions of interest by estimating the density of locations containing the query keywords in the region. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our algorithm.     

Power-aware system-on-chip test scheduling using enhanced rectangle packing algorithm

The current semiconductor technology allows integration of all components onto a single chip called system-on-chip (SoC), which scales down the size of product and improves the performance. When a system becomes more complicated, testing process, such as test scheduling, becomes more challenging. Recently, peak power has also been considered as constraints in the test scheduling problem. Besides these constraints, some add-on techniques including pre-emption and non-consecutive test bus assignment have been introduced. The main contribution of each technique is the reduction of idling time in the test scheduling and thus reducing the total test time. This paper proposes a power-aware test scheduling called enhanced rectangle packing (ERP). In this technique, we formulate the test scheduling problem as the rectangle packing with horizontally and vertically split-able items (rectangles) which are smaller to fill up more compactly the test scheduling floor plan. Experimental results conducted on ITC’02 SoC benchmark circuits revealed positive improvement of the power-aware ERP algorithm in reducing total SoC test time.     

Local polynomial interpolation in a rectangle

The asymptotical error committed by approximating a smooth function by a polynomial is studied. The domain of interpolation is a rectangle in two dimensional space, and the interpolating polynomials belong to the product space of polynomials of degree at most p in one main direction and at most q in the other. For approximating polynomials we consider the use of Taylor and Lagrange interpolation polynomials. Research supported by IAN/CNR (Istituto di Analisi Numerica-CNR) grant 211.01.26, SNF (The Danisch Natural Science Research Council) grant 11-9030 (Jens Hugger) and by the U.S. Office of Naval Research grant N00014-90-J-1030 (Ivo Babuska).