A fast algorithm for the alpha-connected two-center decision problem

This paper considers the problem of determining whether a set of points can be covered by two discs with centers p and q and common radius r, such that the ratio d(p,q)/r is bounded below by a specified constant, α. An O(n²log²n) algorithm for solving this problem is also presented.     

A surface modeling method based on the envelope template

In this paper, we present a novel surface modeling scheme based on an envelope template. A two-parameter family of interpolating surfaces is generated by repeated bicubic interpolation of the given data points, and then a solution to the envelope condition and the envelope of the family are constructed. The continuity conditions of two adjacent patches along the common boundary are derived by analyzing the geometric properties of the envelope patch. In order to facilitate surface modeling, an envelope template is constructed, which has many desirable advantages including simple structure, good local features and so on. G² or C² composite surfaces can be obtained utilizing the envelope template sweeping over the data points.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

The partition of N-dimensional space,using shells

In the field of pattern recognition there are problems where a decision can be made upon a set of training patterns. A training pattern represents a particular known case of the problem under investigation. Here it is represented as a point in the n-dimensional space Rⁿ, where each coordinate denotes a particular parameter of an observation or measurement. Each pattern point belongs to a single answer, which is the solution of this case. In this way, solved examples of the problem under investigation are represented by points of training patterns in the n-dimensional space. The question arises how to make the decision in order to find the answer for a given unknown pattern, i.e. a case without an answer, upon a set of training patterns used as basic knowledge.By the proposed method, shells are used to divide the n-dimensional space into regions where points of training patterns are located. Each shell has the shape of an n-dimensional rectangle and covers pattern points of the same answer. The partition of the n-dimensional space is achieved first in the adaptation phase, where a single shell belongs to the same answer as the pattern points it covers. The coverage of the space obtained after the adaptation phase is then improved in the following self-adaptation phase. Here, pairs of shells belonging to the same answer are merged into substitute shells. Thus, the number of shells is reduced without damage to the obtained quality of the coverage of the space Rⁿ. Upon such a coverage, a decision can be made for a given pattern by searching a shell which covers its pattern point. The answer belonging to this shell is also the answer for that pattern.The efficiency of this model has been satisfactorily demonstrated in two medical fields: prognosis of acute pancreatitis and in the diagnosis of disseminated cancer of unknown origin.     

Chromatic distribution of k-nearest neighbors of a line segment in a planar colored point set

Let P be a set of n colored points distributed arbitrarily in R². The chromatic distribution of the k-nearest neighbors of a query line segment ? is to report the number of points of each color among the k-nearest points of the query line segment. While solving this problem, we have encountered another interesting problem, namely the semicircular range counting query. Here a set of n points is given. The objective is to report the number of points inside a given semicircular range. We propose a simple algorithm for this problem with preprocessing time and space complexity O(n³), and the query time complexity O(logn). Finally, we propose the algorithm for reporting the chromatic distribution of k nearest neighbors of a query line segment. Using our proposed technique for semicircular range counting query, it runs in O(log²n) time.     

A note on linear expected time algorithms for finding convex hulls

Considern independent identically distributed random vectors fromR ^d with common densityf, and letE (C) be the average complexity of an algorithm that finds the convex hull of these points. Most well-known algorithms satisfyE (C)=0(n) for certain classes of densities. In this note, we show thatE (C)=0(n) for algorithms that use a “throw-away” pre-processing step whenf is bounded away from 0 and ∞ on any nondegenerate rectangle ofR ².     

Fully Dynamic Geometric Spanners

In this paper we present an algorithm for maintaining a spanner over a dynamic set of points in constant doubling dimension metric spaces. For a set S of points in ? ^d , a t-spanner is a sparse graph on the points of S such that there is a path in the spanner between any pair of points whose total length is at most t times the distance between the points. We present the first fully dynamic algorithm for maintaining a spanner whose update time depends solely on the number of points in S. In particular, we show how to maintain a (1+ε)-spanner with O(n/ε ^d ) edges, where points can be inserted to S in an amortized update time of O(log?n) and deleted from S in an amortized update time of $\tilde{O}(n^{1/3})$ . As a by-product of our techniques we obtain a simple incremental algorithm for constructing a (1+ε)-spanner with O(n/ε ^d ) edges in constant doubling dimension metric spaces whose running time is O(nlog?n).     

Fast, prime factor, discrete Fourier transform algorithms over GF(2) for 8 ? m ? 10

In this paper it is shown that Winograd’s algorithm for computing convolutions and a fast, prime factor, discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2^m − 1 points over GF(2^m), for 8 ? m ? 10. These new transform techniques can be used to decode Reed-Solomon (RS) codes of block length 2^m − 1. The complexity of this new transform algorithm is reduced substantially from more conventional methods. A computer simulation verifies these new results.     

The circle as a smoothly joined BR-curve on [0, 1]

The full circle as an image of [0, 1] is represented as a BR-curve with five massic vectors (i.e., weighted points or pure vectors). In order to obtain C^k smoothly joined circles, we determine different one-to-one rational changes of parameter. They lead to control polygons consisting in five (respectively seven, nine) massic vectors for k = 1 (respectively k = 3, k = 5). This study is completed by an algorithm and solutions with only positively weighted points.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).     

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.     

2-Covered paths by a set of antennas with minimum power transmission range

In this paper we describe and solve the following geometric optimisation problem: given a set S of n points on the plane (antennas) and two points A and B, find the smallest radial range r∈^ℜ+ (power transmission range of the antennas) so that a path with endpoints A and B exists in which all points are within the range of at least two antennas. The solution to the problem has several applications (e.g., in the planning of safe routes). We present an O(nlogn) time solution, which is based on the second order Voronoi diagram. We also show how to obtain a path with such characteristics.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

On constructing the relative neighborhood graphs in EuclideanK-dimensional spaces

In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of ann points set in Euclideank-dimensional space is presented, for fixedk≥3. The worst case running time of the algorithm isO(n ^2?a(k) (logn)^1?a(k) ), fora(k)=2^?(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms needO(n ²) time. Our algorithm proceeds in two phases. First, a supergraph ofRNG withO(n) edges is constructed and then those edges which do not belong toRNG are eliminated.     

A note on the average number of RSA fixed points

Recently, Chmielowiec (2010) [3] studied an upper bound for the average number of fixed points in RSA encryption and asserted that it is on the order of (logn)² for randomly chosen RSA parameters (n,e). In this paper, we point out some error in his estimation and present detailed procedures for correct evaluation. It is shown that the expected number of RSA fixed points is in fact O((logn)³).     

SU: An efficient algorithm for optimal integrated points placement in hybrid optical-wireless access networks

Integration of optical and wireless networks is considered as one of the promising technologies for next generation Internet access. In this paper, we consider the integrated points placement problem in the hybrid optical-wireless system for optimal resource utilization under the given constraints including hop count, cluster size, and relay load. While the optimization formulation is an NP-hard problem in general, we propose a polynomial-time heuristic algorithm - S²U algorithm to obtain the near-optimal solution that minimizes the number of integrated points required to support all wireless BSs residing in the wireless part of the integrated system. In contrast to the existing work, our S²U algorithm forms the clusters starting from the network edge towards its center and the construction of clusters is not only based on the greedy idea but also considers load balancing. We present a theoretical analysis of the complexity of the proposed S²U algorithm and its approximation ratio to the optimal solution. Furthermore, we present extensive numerical results to compare the proposed S²U algorithm with the main existing methods. It is shown that S²U can not only cover a network with a smaller number of integrated points, but also achieve better network performance in terms of the average transmission delay (average hop count) and load balance. In addition, we compare our results with the optimal solution obtained via CPLEX in terms of the minimum number of integrated points. The results show that the gap between the results obtained from our S²U algorithm and the optimal results is within 5% in average.     

Smallest k-point enclosing rectangle and square of arbitrary orientation

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(?n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn²(n−k)logn) time.     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

Non-partitionable point sets

Let S be a finite set of n points in d-dimensional space. S is α(n)-partitionable if there exists a set of d mutually intersecting hyperplanes that divide d-space into 2^d open regions, no 2^d ? 1 of which together contain more than α(n) points of S. Willard (1982) has shown that every set in 2-space is $\text{3}\text{4}$n-partitionable. Yao (1983) has shown that every set in 3-space is $\text{23}\text{24}$n-partitionable. It is shown here that there exist sets S of arbitrary cardinality in d-space, d ? 5, for which d² + 1 open regions together contain at least n ? d² points of S, in any partition by d intersecting hyperplanes. Further, at least 2^d ? d² ? 1 open regions contain no points of S. This implies that the powerful balanced quad and oct-trees introduced by the above authors may not be generalized to balanced 2^d-trees in dimension at least 5.