A DETERMINISTIC LINEAR TIME ALGORITHM FOR GEOMETRIC SEPARATORS AND ITS APPLICATIONS

1995/01/01 by David Eppstein, Gary L. Miller, Shang‐Hua Teng · 23 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Complexity and Algorithms in Graphs #Dimension (graph theory) #Algorithm #Separator (oil production) #Mathematics #Time complexity #Spacetime #Combinatorics #Discrete mathematics #Physics

paper · doi:10.3233/fi-1995-2241

published in Fundamenta Informaticae 22(4), 309-329 (IOS Press)

openalex publication_date 1995/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

We give a deterministic linear time algorithm for finding a “good” sphere separator of a k-ply neighborhood system Φ in any fixed dimension, where a k-ply neighborhood system in \IR d is a collection of n balls such that no points in the space is c

Citations

• Separator based parallel divide and conquer in computational geometry
• Applications of a Planar Separator Theorem
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• A Separator Theorem for Planar Graphs
• The analysis of a nested dissection algorithm
• Generalized Nested Dissection
• Nested Dissection of a Regular Finite Element Mesh

Cited by

• Planar separator theorem [wikipedia]