Search

Your search keyword '"Frank Dehne"' showing total 9 results
Start Over "Frank Dehne" Publisher springer-verlag
9 results on '"Frank Dehne"'

1. An O(N4) algorithm to construct all Voronoi diagrams for k nearest neighbor searching

Author

Frank Dehne

Subjects
Spacetime, Nearest neighbor graph, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Nearest neighbor search, Nearest-neighbor chain algorithm, Euclidean geometry, MathematicsofComputing_GENERAL, Mathematics::Metric Geometry, Voronoi diagram, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, k-nearest neighbors algorithm
Abstract

This paper presents an algorithm, that constructs all Voronoi diagrams for k nearest neighbor searching in the Euclidean plane simultaneously. Its space and time complexity of O(N4) is shown to be optimal.

Published
2006
Full Text
View/download PDF

2. Coarse grained parallel Monte Carlo algorithms for solving SLAE using PVM

Author

Frank Dehne, Keith Taft, Andrew Rau-Chaplin, and Vassil Alexandrov

Subjects
ComputingMethodologies_SIMULATIONANDMODELING, Stochastic process, Computer science, Numerical analysis, Monte Carlo method, Parallel algorithm, Markov chain Monte Carlo, Hybrid Monte Carlo, Algebraic equation, Matrix (mathematics), symbols.namesake, Bounded function, symbols, Monte Carlo integration, Quasi-Monte Carlo method, Algorithm
Abstract

The problem of solving System of Linear Algebraic Equations (SLAE) by parallel Monte Carlo numerical methods is considered. Three Monte Carlo algorithms are presented. In case when copy of the matrix is sent to each processor the execution time for solving SLAE by Monte Carlo on p processors is bounded by O(nNT/p) (excluding the initial loading of the data) where N is the number of chains and T is the length of the chain in the stochastic process, which are independent of matrix size n.

Published
1998
Full Text
View/download PDF

9. Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time

Author

Maurizio Patrignani, Giuseppe Di Battista, Patrizio Angelini, Frank Dehne, Joerg-Ruediger Sack, Norbert Zeh, Angelini, Patrizio, DI BATTISTA, Giuseppe, and Patrignani, Maurizio

Subjects
Discrete mathematics, Book embedding, Planar straight-line graph, Graph embedding, Butterfly graph, Planar graph, Combinatorics, symbols.namesake, Outerplanar graph, Graph minor, symbols, Polyhedral graph, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Consider an n-vertex planar graph G. We present an O(n^4)-time algorithm for computing an embedding of G with minimum distance from the external face. This bound improves on the best previous bound by an O(n log(n)) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum depth embedding.

Published
2007

Catalog

Books, media, physical & digital resources
See catalog results