Geometric Mesh Partitioning: Implementation and Experiments
- 1 November 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 19 (6) , 2091-2110
- https://doi.org/10.1137/s1064827594275339
Abstract
We investigate a method of dividing an irregular mesh into equal-sized pieces with few interconnecting edges. The method's novel feature is that it exploits the geometric coordinates of the mesh vertices. It is based on theoretical work of Miller, Teng, Thurston, and Vavasis, who showed that certain classes of "well-shaped" finite-element meshes have good separators. The geometric method is quite simple to implement: we describe a \sc Matlab code for it in some detail. The method is also quite efficient and effective: we compare it with some other methods, including spectral bisection.Keywords
This publication has 26 references indexed in Scilit:
- On the Optimality of the Median Cut Spectral Bisection Graph Partitioning MethodSIAM Journal on Scientific Computing, 1997
- APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTSInternational Journal of Computational Geometry & Applications, 1996
- On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraintNumerical Algorithms, 1996
- Linear-size nonobtuse triangulation of polygonsDiscrete & Computational Geometry, 1995
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanicsInternational Journal for Numerical Methods in Engineering, 1993
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- An Algorithm for Partitioning the Nodes of a GraphSIAM Journal on Algebraic Discrete Methods, 1982
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973
- Coverings of Bipartite GraphsCanadian Journal of Mathematics, 1958