An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

A fast algorithm for determining the distances of the points of a given set in an integral lattice from its complement

A linear-time algorithm is proposed for determining the distances of the points of a given set in an r-dimensional integral lattice from its complement.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 177–181, March–April, 1992.     

Reconstructing domain boundaries within a given set of points,using Delaunay triangulation

Given an input set of planar points, which occupy a non-convex polygon area, possibly with holes, we reconstruct the shape of its boundary domain, without previous knowledge of which points or edges belong to the boundary. Our approach is based on different qualities of the Delaunay triangles inside and outside the domain. This method is heuristic and does not ensure success in all cases but it is very simple and there is no other method for this problem known to us. The method was derived on real GIS data but experiments show that it could also be used for mechanical engineering data, with positive results.     

An algorithm for selecting main points on a line

We describe a new method for selecting the main points in a set of points which describe a line based on an assigned tolerance. This method is precise, fast and local. We also present a FORTRAN implementation of the algorithm and some applications to problems of automated cartography.     

一种参考能量的最小连通支配集近似算法

在无线传感器网络中,能量效率问题至关重要,构造精简的虚拟骨干网可以节约有限资源,这等同于在图论中求解最小连通支配集(MCDS)问题.由此,提出一种构造MCDS的启发式算法.首先根据均值公式为顶点建立次序表,其次构造极大独立集(MIS),再次连接MIS节点,最后优化.仿真实验表明:该算法能够在短时间内找到规模较小的连通支配集(CDS),并且有效地均衡了各节点能量,延长了网络生命周期.     

HyperMask – projecting a talking head onto a real object

Published online: 15 March 2002     

An algorithm for connectingN points with a minimum number of crossings

C. Y. LEE has given [1] an algorithm for connecting two points with a path optimal with reference to given functions. In the case of planar paths and for the optimisation of the number of crossings the above algorithm assumes the simplified form presented in «SIMPLIFICATION OF LEE'S ALGORITHM FOR SPECIAL PROBLEMS» by E. Majorani, also included in this n⁰ of «CALCOLO». This article extends such a simplified algorithm (which in the two point case will be calledsimple algorithm) to then-terminal case. The extention is far from being obvious, when the required path has to be rigorously optimal. The algorithm has been programmed for the OLIVETTI ELEA 9003 computer.     

基于熵自加权联合正则化最近点的图像集分类算法

图像集分类算法通过充分利用图像的集合信息来提高识别性能,得到了广泛的关注。但是现有的图像集分类算法存在如下问题：1）需要样本满足某种概率统计分布;2）忽略了图库集类与类之间的互斥性;3）对非高斯噪声不具备鲁棒性。为了解决上述问题,提出了一种基于熵自加权联合正则化最近点的图像集分类算法（SRNPC）。首先在测试集中寻找唯一的全局联合正则化最近点,同时最小化该点与每个图库集中正则化最近点之间的距离;然后,为了增强类之间的判别力以及对非高斯噪声的鲁棒性,引入一种基于熵尺度的自加权策略来迭代更新测试集与各个图库集合之间的熵加权权重,得到的权重能够直接反映测试集与每个图库集之间相关性的高低;最后,利用测试集和每个图库集之间的最小残差值获得分类结果。通过在UCSD/Honda、CMU Mobo和YouTube这三个公开数据集上与当前主流的算法进行的对比实验结果表明,所提出的算法具有更高的分类精度和更强的鲁棒性。     

An optimal distributed algorithm for finding articulation points in a network

This paper presents a distributed algorithm for finding the articulation points in an n node communication network represented by a connected undirected graph. For a given graph if the deletion of a node splits the graph into two or more components then that node is called an articulation point. The output of the algorithm is available in a distributed manner, i.e., when the algorithm terminates each node knows whether it is an articulation point or not. It is shown that the algorithm requires O(n) messages and O(n) units of time and is optimal in communication complexity to within a constant factor.     

An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.     

Approximation of a set of points by points of a grid

A procedure is given for translating a rectangular grid in such a way that a finite set of points in ?^N is approximated as good as possible by points of the translated grid.     

An active set algorithm for tracing parametrized optima

Optimization problems often depend on parameters that define constraints or objective functions. It is often necessary to know the effect of a change in a parameter on the optimum solution. An algorithm is presented here for tracking paths of optimal solutions of inequality constrained nonlinear programming problems as a function of a parameter. The proposed algorithm employs homotopy zero-curve tracing techniques to track segments where the set of active constraints is unchanged. The transition between segments is handled by considering all possible sets of active constraints and eliminating nonoptimal ones based on the signs of the Lagrange multipliers and the derivatives of the optimal solutions with respect to the parameter. A spring-mass problem is used to illustrate all possible kinds of transition events, and the algorithm is applied to a well-known ten-bar truss structural optimization problem.     

An algorithm to establish whether a given rectangular array is a sub-array of a rectangular array also given

The scope of this paper is to find an algorithm that makes it possible to establish wheter a given rectangular arrayX _rs is a sub-array of a rectangular arrayA _mn (r≤m, s≤n) also given and if so to locate all the possible choices ofm−r rows andn−s columns to be deleted fromA _mn to obtainX _rs .     

Drawing curves onto a cloud of points for point-based modelling

Point-based geometric models are gaining popularity in both the computer graphics and CAD fields. A related design/modelling problem is the focus of the reported research: drawing curves onto digital surfaces represented by clouds of points. The problem is analyzed and solved, and a set of ‘design tools’ are proposed which allow the user/designer to efficiently perform ‘product development’ (alternative name: ‘detail design’) tasks which require efficient processing of a ‘digital surface’. The primary tool is a robust and efficient point projection algorithm combined with a smoothing technique for producing smooth ‘digital curves’ lying onto the cloud surface. The new design tools are tested on a real-life industrial example with very satisfactory results, which are thoroughly presented in the paper.     

An output sensitive algorithm for computing a maximum independent set of a circle graph

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,α}) time at worst, for an n vertex circle graph where α is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Θ(nd) time at worst.     

An algorithm for uniform random sampling of points in and on a hypersphere

A new algorithm, based on a set of generalized polar coordinates, is given for uniform random sampling of points in the interior or on the surface of an N-dimensional hypersphere. Computation times are compared for a variety of algorithms on several high-speed computers.