5430292
A practical evaluation of kinetic data structures
In many applications of computational geometry to modeling objects and processes in the physical world, the participating objects are in a state of continuous change. Motion is the most ubiquitous kind of continuous transformation but others, such as shape deformation, are also possible. In a recent paper, Baech, Guibas, and Hershberger [BGH97] proposed the framework of kinetic data structures (KDSS) as a way to maintain, in a completely on-line fashion, desirable information about the state of a geometric system in continuous motion or change. They gave examples of kinetic data structures for the maximum of a set of (changing) numbers, and for the convex hull and closest pair of a set of (moving) points in the plane. The KDS frameworkallowseach object to change its motion at will according to interactions with other moving objects, the environment, etc. We implemented the KDSSdescribed in [BGH97],es well as came alternative methods serving the same purpose, as a way to validate the kinetic data structures framework in practice. In this note, we report some preliminary results on the maintenance of the convex hull, describe the experimental setup, compare three alternative methods, discuss the value of the measures of quality for KDSS proposed by [BGH97],and highlight some important numerical issues.
100573
A hierarchical method for real-time distance computation among moving convex bodies
Abstract This paper presents the Hierarchical Walk , or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For convex polygons, we prove that H-Walk improves on the classic Lin–Canny and Dobkin–Kirkpatrick algorithms. We have implemented H-Walk for moving convex polyhedra in three dimensions. Experimental results indicate that, unlike previous incremental distance computation algorithms, H-Walk adapts well to variable coherence in the motion and provides consistent performance.
11907465
Deformable Free-Space Tilings for Kinetic Collision Detection†
We present kinetic data structures for detecting collisions between a set of polygons that are moving continuously. Unlike classical collision detection methods that rely on bounding volume hierarchies, our method is based on deformable tilings of the free space surrounding the polygons. The basic shape of our tiles is that of a pseudo-triangle, a shape sufficiently flexible to allow extensive deformation, yet structured enough to make detection of self-collisions easy. We show different schemes for maintaining pseudo-triangulations as a kinetic data structure, and we analyze their performance. Specifically, we first describe an algorithm for maintaining a pseudo-triangulation of a point set, and show that the pseudo-triangulation changes only quadratically many times if points move along algebraic arcs of constant degree. In addition, by refining the pseudo-triangulation, we show triangulations of points that only change about O(n 7 / 3 ) times for linear motion. We then describe an algorithm for maintaining a pseudo-triangulation of a set of convex polygons. Finally, we extend our algorithm to the general case of maintaining a pseudo-triangulation of a set of moving or deforming simple polygons.
5478794
Euclidean proximity and power diagrams
Power diagrams [Aur87] are a useful generalization of Voronoi diagrams in which the sites defining the diagram are not points but balls. They derive their name from the fact that the distance used in their definition is not the standard Euclidean distance, but instead the classical notion of the power of a point with respect to a ball [Cox61]. The advantage of the power distance is that the ‘bisector surfaces’, the surfaces equidistant from two given balls, are hyper-planes, and thus the Euclidean structure of these diagrams is polyhedral and they are easier to compute and manipulate than standard Voronoi diagrams. Several algorithms and applications for the power diagrams are already known, including those referenced in [IIM85, Aur88]. Most recently power diagrams have played a key role in work related to alpha shapes and ‘skins’ [Ede93, EM94, Ede95], as collections of balls are a natural model for molecular structures. The Voronoi diagram of point sites in any dimension has many useful proximity properties. Let us say that two sites are neighbors in the Voronoi diagram if their Voronoi cells share a common facet. It is well known that, for a set of points S, the closest pair of points in S are neighbors in the Voronoi diagram of S — equivalently, the closest pair of points must define an edge of the dual Delaunay diagram. Even more is true: the nearest neighbor to any point p ∈ S is a neighbor to p in the Voronoi diagram (equivalently, is connected to this neighbor by a Delaunay edge). Surprisingly, it seems that analogous proximity properties have not been studied for the power diagram. In this note, we consider the the power diagram of a set of disjoint balls. We show that the closest pair of
9735559
Probabilistic analysis for combinatorial functions of moving points
We initiate a probabilistic study of configuration functions of moving points. In our probabilistic model, a particle is given an initiaf position and a velocity drawn independently at random from the same distribution D. We show that if n particles are drawn independently at random from the uniform distribution on the square, their convex hull undergoes El(logz n) combinatorial changes in expectation, their Voronoi diagram undergoes e(n312 ) combinatorial changes, and their closest pair undergoes El(n) combinatorial changes.
174192
Fault tolerant networks with small degree
In this paper, we study the design of fault tolerant networks for arrays and meshes by adding redundant nodes and edges. For a target graph <italic>G</italic> (linear array or mesh in this paper), a graph <italic>G</italic>′ is called a &kgr;-fault-tolerant graph of <italic>G</italic> if when we remove any &kgr; nodes from <italic>G</italic>′, it still contains a subgraph isomorphic to <italic>G</italic>. The major quality measures for a fault-tolerant graph are the number of spare nodes it uses and the maximum degree it has. The degree is particularly important in practice as it poses constraints on the scalability of the system. In this paper, we aim at designing fault-tolerant graphs with both small degree and small number of spare nodes. The graphs we obtain have degree <italic>O</italic>(1) for arrays and <italic>O</italic>(log<supscrpt>3</supscrpt> &kgr;) for meshes. The number of spare nodes used are <italic>O</italic>(&kgr; log<supscrpt>2</supscrpt> &kgr;) and <italic>O</italic>(&kgr;<supscrpt>2</supscrpt>/log &kgr;), respectively. Compared to the previous results, the number of spare nodes used in our construction has one fewer linear factor in &kgr;.
18035076
On Subsumption Removal and On-the-Fly CNF Simplification
CNF Boolean formulas generated from resolution or solution enumeration often have much redundancy. Efficient algorithms are needed to simplify and compact such CNF formulas. In this paper, we present a novel algorithm to maintain a subsumption-free CNF clause database by efficiently detecting and removing subsumption as the clauses are being added. We then present an algorithm that compact CNF formula further by applying resolutions to make it Decremental Resolution Free. Our experimental evaluations show that these algorithms are efficient and effective in practice.
18758619
IGroup: a web image search engine with semantic clustering of search results
In this demo, we present IGroup, a Web image search engine that organizes the search results into semantic clusters. Different from all existing Web image search results clustering algorithms that only cluster the top few images using visual or textual features, IGroup first identifies several query-related semantic clusters based on a key phrases extraction algorithm originally proposed for clustering general Web search results. Then, all the resulting images are separated and assigned to corresponding clusters. To make the best use of the clustering results, a new user interface is proposed. Please go to http://igroup.msra.cn for real experience.
6035916
Ranking web objects from multiple communities
Vertical search is a promising direction as it leverages domain-specific knowledge and can provide more precise information for users. In this paper, we study the Web object-ranking problem, one of the key issues in building a vertical search engine. More specifically, we focus on this problem in cases when objects lack relationships between different Web communities, and take high-quality photo search as the test bed for this investigation. We proposed two score fusion methods that can automatically integrate as many Web communities (Web forums) with rating information as possible. The proposed fusion methods leverage the hidden links discovered by a duplicate photo detection algorithm, and aims at minimizing score differences of duplicate photos in different forums. Both intermediate results and user studies show the proposed fusion methods are practical and efficient solutions to Web object ranking in cases we have described. Though the experiments were conducted on high-quality photo ranking, the proposed algorithms are also applicable to other ranking problems, such as movie ranking and music ranking.
8611890
Relevancy based semantic interoperation of reuse repositories
Software reuse is a promising solution to the software crisis. Reuse repositories are the basic infrastructure for software reuse. During the past decade, various academic, commercial, governmental, and industrial organizations have developed many Internet-enabled reuse repositories to provide access to software components and related resources. It has necessitated semantic interoperation to allow distributed maintenance and management of these repositories while enabling users to efficiently and conveniently access resources from multiple reuse repositories via a single representation view. In this paper, we have proposed an approach to enhancing the semantic interoperability of reuse repositories, called the improved relevancy matching and ranking (IRMR) method, based on analyzing the correlation of terms in representation methods of the repositories. A prototype system, the Virtual Repository supporting Semantic Interoperation (VRSI), is presented to illustrate the application of this approach to support the semantic interoperation of reuse repositories. Experimental results on real world reuse repositories demonstrated significant improvement in terms of searching effectiveness.
10515113
Validating SAT solvers using an independent resolution-based checker: practical implementations and other applications
As the use of SAT solvers as core engines in EDA applications grows, it becomes increasingly important to validate their correctness. In this paper, we describe the implementation of an independent resolution-based checking procedure that can check the validity of unsatisfiable claims produced by the SAT solver zchaff. We examine the practical implementation issues of such a checker and describe two implementations with different pros and cons. Experimental results show low overhead for the checking process. Our checker can work with many other modern SAT solvers with minor modifications, and it can provide information for debugging when checking fails. Finally we describe additional results that can be obtained by the validation process and briefly discuss their applications.