多连通多边形的内部Voronoi图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

矩阵条件数及高斯算法平滑分析的进一步研究

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.     

网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.     

基于距离不等式的K-medoids聚类算法

本文研究加速K-medoids聚类算法,首先以PAM（Partitioning Around Medoids）、TPAM（Triangular Inequality Elimination Criteria PAM）算法为基础,给出两个加速引理,并基于中心点之间距离不等式提出两个新加速定理.同时,以O（n+K²）额外内存空间开销辅助引理、定理的结合而提出加速SPAM（Speed Up PAM）聚类算法,使得K-medoids聚类算法复杂度由O（K（n-K）²）降低至O（（n-K）²）.在实际及人工模拟数据集上的实验结果表明,相对PAM、TPAM、FKMEDOIDS（Fast K-medoids）等参考算法均有改进,运行时间比PAM至少提升0.828倍.     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

无向图的边极大匹配并行算法及其应用*

在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

A linear-time algorithm for constructing a circular visibility diagram

To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers results in a planar partition called the circular visibility diagram. AnO(n) algorithm is given for constructing the circular visibility diagram for a simple polygon withn vertices.     

Mapping Simple Polygons: How Robots Benefit from Looking Back

We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other. Our results are tight in the sense that the strong rendezvous problem, where robots need to gather at a vertex, cannot be solved in general, and, without knowing a bound beforehand, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known.     

Industrial strength polygon clipping: A novel algorithm with applications in VLSI CAD

We present an algorithm to compute the topology and geometry of an arbitrary number of polygon sets in the plane, also known as the map overlay. This algorithm can perform polygon clipping and related operations of interest in VLSI CAD. The algorithm requires no preconditions from input polygons and satisfies a strict set of post conditions suitable for immediate processing of output polygons by downstream tools. The algorithm uses sweepline to compute a Riemann–Stieltjes integral over polygon overlaps in O((n+s)log(n)) time given n polygon edges with s intersections. The algorithm is efficient and general, handling degenerate inputs implicitly. Particular care was taken in implementing the algorithm to ensure numerical robustness without sacrificing efficiency. We present performance comparisons with other polygon clipping algorithms and give examples of real world applications of our algorithm in an industrial software setting.     

On partitioning rectilinear polygons into star-shaped polygons

We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.     

An optimal visibility graph algorithm for triangulated simple polygons

LetP be a triangulated simple polygon withn sides. The visibility graph ofP has an edge between every pair of polygon vertices that can be connected by an open segment in the interior ofP. We describe an algorithm that finds the visibility graph ofP inO(m) time, wherem is the number of edges in the visibility graph. Becausem can be as small asO(n), the algorithm improves on the more general visibility algorithms of Asanoet al. [AAGHI] and Welzl [W], which take (n ²) time, and on Suri'sO(m logn) visibility graph algorithm for simple polygons [S].This work was supported in part by a U.S. Army Research Office fellowship under agreement DAAG29-83-G-0020.     

An exact algorithm for minimizing vertex guards on art galleries

We consider the problem [art gallery problem (AGP)] of minimizing the number of vertex guards required to monitor an art gallery whose boundary is an n‐vertex simple polygon. In this paper, we compile and extend our research on exact approaches for solving the AGP. In prior works, we proposed and tested an exact algorithm for the case of orthogonal polygons. In that algorithm, a discretization that approximates the polygon is used to formulate an instance of the set cover problem, which is subsequently solved to optimality. Either the set of guards that characterizes this solution solves the original instance of the AGP, and the algorithm halts, or the discretization is refined and a new iteration begins. This procedure always converges to an optimal solution of the AGP and, moreover, the number of iterations executed highly depends on the way we discretize the polygon. Notwithstanding that the best known theoretical bound for convergence is Θ(n³) iterations, our experiments show that an optimal solution is always found within a small number of them, even for random polygons of many hundreds of vertices. Herein, we broaden the family of polygon classes to which the algorithm is applied by including non‐orthogonal polygons. Furthermore, we propose new discretization strategies leading to additional trade‐off analysis of preprocessing vs. processing times and achieving, in the case of the novel Convex Vertices strategy, the most efficient overall performance so far. We report on experiments with both simple and orthogonal polygons of up to 2500 vertices showing that, in all cases, no more than 15 minutes are needed to reach an exact solution, on a standard desktop computer. Ultimately, we more than doubled the size of the largest instances solved to optimality compared with our previous experiments, which were already five times larger than those previously reported in the literature.     

Time-Optimal Nearest-Neighbor Computations on Enhanced Meshes

The All Nearest Neighbor problem (ANN, for short) is stated as follows: given a setSof points in the plane, determine for every point inS, a point that lies closest to it. The ANN problem is central to VLSI design, computer graphics, pattern recognition, and image processing, among others. In this paper we propose time-optimal algorithms to solve the ANN problem for an arbitrary set of points in the plane and also for the special case where the points are vertices of a convex polygon. Both our algorithms run on meshes with multiple broadcasting. Our first main contribution is to establish an Ω(logn) time lower bound for the task of solving an arbitraryn-point instance of the ANN problem, even if the points are the vertices of a convex polygon. We obtain our time lower bound results for the CREW-PRAM by using a novel technique involving geometric constructions. These constructions allow us to reduce the well-known OR problem to each of the geometric problems of interest. We then port these time lower bounds to the mesh with multiple broadcasting using simulation results. Our second main contribution is to show that the time lower bound obtained is tight, by exhibiting algorithms solving the problem inO(logn) time on a mesh with multiple broadcasting of sizen×n.     

Complexity,convexity, and unimodality

A class of polygons termedunimodal is introduced. LetP = P₁,p ₂,...,p _n be a simplen-vertex polygon. Given a fixed vertex or edge, several definitions of the distance between the fixed vertex or edge and any other vertex or edge are considered. For a fixed vertex (edge), a distance measure defines a distance function as the remaining vertices (edges) are traversed in order. If for every vertex (edge) ofP a specified distance function is unimodal thenP is a unimodal polygon in the corresponding sense. Relationships between unimodal polygons, in several senses, andconvex polygons are established. Several properties are derived for unimodal polygons when the distance measure is the euclidean distance between vertices of the polygons. These properties lead to very simple 0(n) algorithms for solving a variety of problems that occur in computational geometry and pattern recognition. Furthermore, these algorithms establish that convexity is not the key factor in obtaining linear-time-complexity for solving these problems. The paper closes with several open questions in this area.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.