1,721,045 research outputs found
Robust Proximity Queries: An Illustration of Degree-driven Algorithms Design
No full textIn the context of methodologies intended to confer robustness to geometric algorithms,
we elaborate on the exact-computation paradigm and formalize the notion of degree of a
geometric algorithm as a worst-case quantification of the precision (number of bits) to which arithmetic
calculation have to be executed in order to guarantee topological correctness. We also propose
a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm
and an illustration of our general approach where algorithm design is driven also by the degree,
we consider the important classical problem of proximity queries in two and three dimensions and
develop a new technique for the efficient and robust execution of such queries based on an implicit
representation of Voronoi diagrams. Our new technique offers both low degree and fast query time
and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number
of operations, and arithmetic degree
Graph ALgorithms and Applications 4
No full textThis book contains Volume 7 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 4 presents contributions from prominent authors and includes selected papers from (a) the Seventh International Workshop on Algorithms and Data Structures (WADS 2001) and (b) the 2001 Symposium on Graph Drawing (GD 2001). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry (C Barrett et al.)
* On External-Memory Planar Depth First Search (L Arge et al.)
* Finding Shortest Paths with Computational Geometry (P-S Loh)
* Polar Coordinate Drawing of Planar Graphs with Good Angular Resolution (C Duncan & S Kobourov)
* and other paper
Graph Algorihms and Applications 3
No full textThis book contains Volume 6 of the Journal of Graph Algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit design.
Graph Algorithms and Applications 3 presents contributions from prominent authors and includes selected papers from the Symposium on Graph Drawing (1999 and 2000). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.
Contents:
* Triangle-Free Planar Graphs and Segment Intersection Graphs (N de Castro et al.)
* Traversing Directed Eulerian Mazes (S Bhatt et al.)
* A Fast Multi-Scale Method for Drawing Large Graphs (D Harel & Y Koren)
* GRIP: Graph Drawing with Intelligent Placement (P Gajer & S G Kobourov)
* Graph Drawing in Motion (C Friedrich & P Eades)
* A 6-Regular Torus Graph Family with Applications to Cellular and Interconnection Networks (M Iridon & D W Matula)
* and other paper
The Mocha Algorithm Animation System
No full textWe describe the implementation of a new system, called Mocha, for providing algorithm animation over the World Wide Web. Mocha is a distributed system with a client-server architecture that optimally partitions the software components of a typical algorithm animation system, and leverages the power of the Java language, an emerging standard for distributing interactive platform-independent applications across the Web
Checking the Convexity of Polytopes and the Planarity of Subdivisions
No full textThis paper studies the problem of verifying the correctness of geometric structures. We design optimal checkers for convex polytopes in two and higher dimensions, and for various types of planar subdivisions, such as triangulations, Delaunay triangulations, and convex subdivisions. Our checkers are simpler and more general than the ones previously described in the literature. Their performance is studied also in terms of the degree, which characterizes the arithmetic precision required
- …
