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.     

Optimal randomized parallel algorithms for computational geometry

We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn ). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.This is a substantially revised version of the paper that appeared as Optimal Randomized Parallel Algorithms for Computational Geometry in theProceedings of the 16th International Conference on Parallel Processing, St. Charles, Illinois, August 1987.This research was supported by DARPA/ARO Contract DAAL03-88-K-0195, Air Force Contract AFOSR-87-0386, DARPA/ISTO Contracts N00014-88-K-0458 and N00014-91-J-1985, and by NASA Subcontract 550-63 of Primecontract NAS5-30428.     

Dynamic Connectivity for Axis-Parallel Rectangles

In this paper we give a fully dynamic data structure to maintain the connectivity of the intersection graph of n axis-parallel rectangles. The amortized update time (insertion and deletion of rectangles) is and the query time (deciding whether two given rectangles are connected) is O(1). It slightly improves the update time (O(n ^0.94)) of the previous method while drastically reducing the query time (near O(n ^1/3)). In addition, our method does not use fast matrix multiplication results and supports a wider range of queries. This work has been supported by an NSERC grant.     

Shortest paths in simple polygons with polygon-meet constraints

We study a constrained version of the shortest path problem in simple polygons, in which the path must visit a given target polygon. We provide a worst-case optimal algorithm for this problem and also present a method to construct a subdivision of the simple polygon to efficiently answer queries to retrieve the shortest polygon-meeting paths from a single-source to the query point. The algorithms are linear, both in time and space, in terms of the complexity of the two polygons.     

A workbench for computational geometry

We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, Carleton University, and the Univeristy of Passau. Work on this project was carried out in part while A. Knight and J.-R. Sack were at the University of Passau.     

Dynamic bin packing with unit fraction items revisited

In this paper, we will study the problem of dynamic bin packing with unit fraction items. We focus on analyzing the First Fit (FF) algorithm on this problem. There are two main results: i) we give the first bound for the FF algorithm on cases when the largest item is at most 1/k; ii) we generalize the previous framework for analyzing FF and get an improved upper bound.     

A meeting scheduling problem respecting time and space

We consider the problem of determining suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In particular, we give two solutions to the problem instance where each participant has two scheduled meetings separated by a free time interval. We present an O(n logn) algorithm for n participants obtained by purely geometrical arguments. Our second approach uses the concept of LP-type problems and leads to a randomized algorithm with expected running time O(n). We also consider a graph-based model where participants belong to different groups and can travel along the edges of a graph. For the meeting, only one member out of each group is required. The resulting problem can be solved using furthest color Voronoi diagrams on graphs.

Drawing K2,n: A lower bound

We give a tradeoff theorem between the area and the aspect ratio required by any planar straight-line drawing of K_2,n on the integer lattice. In particular we show that if the drawing is contained in a rectangle of area O(n) then the rectangle must have aspect ratio , and conversely, if the aspect ratio is O(1) then the area must be .     

A new approximation algorithm for labeling points with circle pairs

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in time and O(n) space and achieves an approximation factor of (≈1.486+ε), which improves the previous best bound of 1.491+ε.     

A lower bound for computing Oja depth

Let S={s₁,…,sn} be a set of points in the plane. The Oja depth of a query point θ with respect to S is the sum of the areas of all triangles (θ,si,sj). This depth may be computed in O(nlogn) time in the RAM model of computation. We show that a matching lower bound holds in the algebraic decision tree model. This bound also applies to the computation of the Oja gradient, the Oja sign test, and to the problem of computing the sum of pairwise distances among points on a line.     

A new algorithm for the largest empty rectangle problem

A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).     

A note on 3D orthogonal drawings with direction constrained edges

The recent interest in three-dimensional graph drawing has been motivating studies on how to extend two-dimensional techniques to higher dimensions. A common 2D approach for computing an orthogonal drawing separates the task of defining the shape of the drawing from the task of computing its coordinates. First results towards finding a three-dimensional counterpart of this approach are presented by G. Di Battista, et al. [Graph Drawing (Proc. GD'00), Lecture Notes in Comput. Sci., vol. 1984, Springer, Berlin, 2001; Theoret. Comput. Sci. 289 (2002) 897], where characterizations of orthogonal representations of paths and cycles are studied. In this paper we show that the characterization for cycles given by G. Di Battista, et al. [Theoret. Comput. Sci. 289 (2002) 897] does not immediately extend to even seemingly simple graphs.     

动态企业信息系统解决方案

本文阐述了一种采用动态方式构筑的企业信息系统,该信息系统可以在企业运行规则发生变化时,由操作人员及时的进行调整,适应新的规则。     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

土地信息系统中面向对象数据模型的研究与应用

土地信息系统是以土地资源与资产管理为工作对象的计算机信息系统。土地信息具有综合性、共享性、动态性等特点。在对土地信息系统数据结构和操作进行分析的基础上,对面向对象的土地信息系统数据模型进行了研究。以之为基础进行了农用地分等定级实例对象的封装,并对该对象的内部结构进行了描述。     

一种服务网格动态信息聚合模型及其应用

在动态、跨组织的网格环境中如何进行适应组织重构、业务变化等动态性要求的信息聚合是现实应用中亟待解决的问题．文章提出了服务网格动态信息聚合模型。从组织模型、数据模型、协作模型三个维度描述信息聚合中变化的因素．基于此模型．给出了一种支持动态信息聚合的实现框架,它能够适应网格组织结构变化、业务变化,协调人的参与,进而提高系统动态性．最后介绍了该模型及其实现框架在远程学习评价网格LAGrid中的应用情况．     

加工仿真系统中弯管类零件加工工艺信息的自动提取

在加工仿真系统中 ,加工工艺信息的自动生成对于提高仿真系统的自动化、实用化水平 ,减少工艺人员的工作负荷至关重要。该文针对弯管零件加工仿真系统 ,提出了加工工艺信息自动提取方法。该方法根据弯管零件的数字化模型 ,自动判断曲面的类型 ,生成各曲面间的拓扑关系 ,提取每个曲面的几何参数及相关曲面的位置关系信息 ,并将这些信息转为工艺参数 ,输入工艺知识库 ,再根据相应的工艺知识 ,生成加工工艺信息。     

A coordinate system associated with points scattered on a surface

Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the so-called natural neighbor coordinates that are defined from the Voronoi diagram of the sample points. A drawback of those coordinate systems is that their definition domain is restricted to the convex hull of the sample points. This makes them difficult to use when the sample points belong to a surface. To overcome this diffculty, we propose a new system of coordinates. Given a closed surface S, i.e. a (d−1)-manifold of the coordinate system is defined everywhere on the surface, is continuous, and is local even if the sampling density is finite. Moreover, it is inherently (d−1)-dimensional while the previous systems are d-dimensional. No assumption is made about the ordering, the connectivity or topology of the sample points nor of the surface. We illustrate our results with an application to interpolation over a surface.     

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham’s scan, Andrew’s monotone chain, Jarvis’ gift wrapping, Chan’s, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space.