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.     

一种引入动态词库更新的中文分词架构

针对互联网环境下新词出现和更新频率高的特点,将机械分词与基于规则分词相结合,提出一种动态更新词库的中文分词架构.本架构给出了新的词典设计结构及歧义处理规则,并将统计学中的互信息概念运用到新词判定环节.实验表明本文提出的中文分词架构具有较高的准确率和良好的适应性.     

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.     

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.     

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.     

基于ArcView GIS的数据字典技术研究

随着地理信息系统技术的进一步发展,数据库技术将会成为提升整个系统适应性能的关键技术之一。数据字典技术作为数据库技术的核心内容之一,其重要性体现在系统开发及运行等各个阶段。基于数据字典的研究现状,探讨了“数据字典集”和“字典程序”的概念,并结合ArcView GIS的特点对数据字典技术在地理信息系统中的应用进行了研究。开发实例证明,把字典程序作为系统应用程序访问数据库的中间接口,用于操纵数据字典集以实现系统对数据库的管理,增强了系统进行数据库管理的灵活性、适应性,也便于系统的维护和升级,具有良好的应用前景。     

一种批量抽取动态Web信息系

针对从Web页面获取信息的广泛需求,分析了从中提取信息的关键技术如URL地址、HTML页面和HtmlParse解析库;以从Google Map中获取企业黄页信息为例,根据从中自动提取数据的技术和步骤,设计和实现了该系统原型,并指出的相关问题及其解决办法.     

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 .     

带边界条件约束的非相干字典学习方法及其稀疏表示

从字典的相干性边界条件出发, 提出一种基于极分解的非相干字典学习方法(Polar decomposition based incoherent dictionary learning, PDIDL), 该方法将字典以Frobenius范数逼近由矩阵极分解获取的紧框架, 同时采用最小化所有原子对的内积平方和作为约束, 以降低字典的相干性, 并保持更新前后字典结构的整体相似特性. 采用最速梯度下降法和子空间旋转实现非相干字典的学习和优化. 最后将该方法应用于合成数据与实际语音数据的稀疏表示. 实验结果表明, 本文方法学习的字典能逼近等角紧框架(Equiangular tight-frame, ETF), 实现最大化稀疏编码, 在降低字典相干性的同时具有较低的稀疏表示误差.     

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.     

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

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

“蒙古语名词语义信息词典”的开发与应用

2009年至今,“蒙古语名词语义信息词典”(以下简称为“名词语义词典”)通过几年的开发目前词典基本成形,并且有了显著的新进展。其新进展主要体现在词条的扩充、属性字段的增添及其初步应用。该文概要介绍“名词语义词典”的研发过程,实例说明这部词典的新进展和初步应用情况。     

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

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

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

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

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).