In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large...
详细信息
In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large-scale integrated (VLSI) circuits and architectural databases. We describe an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found. This algorithm is optimal to within a constant factor. As an intermediate step of this algorithm, we solve a problem related to the range searching problem that arises in database applications. Although the algorithms that we describe are primarily theoretical devices (being very difficult to code), they suggest other algorithms that are quite practical.
The kernel K(P) of a simple polygon P wah n verUces is the locus of the points internal to P from which all verUces of P are wslble Equwalently, K(P) is the mtersectmn of appropriate half-planes determined by the poly...
详细信息
Iterations for solving the nonhnear equation F(x) = 0 in N-dimensional Banach space, [formula omitted], which use “integral mformatton with a kernel” are considered This information consists of the “standard reform...
详细信息
This paper considers allocation of space in a hnear storage medium when space must be allocated dynamically as customers arrive A heuristic is proposed for this problem and for a simple model of the resultmg reference...
详细信息
Presents convex hulls of sets of points in two and three dimensions. Relevance of the convex hull on several problems in computer graphics, design automation, pattern recognition and operations research; Technique use...
详细信息
Presents convex hulls of sets of points in two and three dimensions. Relevance of the convex hull on several problems in computer graphics, design automation, pattern recognition and operations research; Technique used in the algorithm.
The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2n-1 which use n evaluations of ƒ and no derivative evaluations, as well as a second...
详细信息
The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2n-1 which use n evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2n-1 based on n — 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth *** is proved that the optimal order of one general class of multipoint iterations is 2n-1 and that an upper bound on the order of a multipoint iteration based on n evaluations of ƒ (no derivatives) is *** is conjectured that a multipoint iteration without memory based on n evaluations has optimal order 2n-1.
An algorithm for the optimal solution of consistent and inconsistent linear inequalities is presented, where the optimality criterion is the maximization of the number of satisfied constraints. The algorithm is develo...
详细信息
The establishment of lower bounds on the number of comparisons necessary to solve various combinatorial problems is considered. Some of the new results are : (a) given two finite sets of real numbers, A and B, where n...
详细信息
暂无评论