Geometric Separator Theorems & Applications

We find a large number of "geometric separator theorems" such as: I: Given N disjoint isooriented squares in the plane, there exists a rectangle with /spl les/2N/3 squares inside, /spl les/2N/3 squares outside, and /spl les/(4+0(1))/spl radic/N partly in & out. II: There exists a rectangle that is crossed by the minimal spanning tree of N sites in the plane at /spl les/(4/spl middot/3/sup 1/4/+0(1))/spl radic/N points, having /spl les/2N/3 sites inside and outside. These theorems yield a large number of applications, such as subexponential algorithms for traveling salesman tour and rectilinear Steiner minimal tree in R/sup d/, new point location algorithms, and new upper and lower bound proofs for "planar separator theorems".

Authors

• Warren D. Smith
• Nicholas C. Wormald

Keywords

• Particle separators
• Steiner trees
• Traveling salesman problems
• Tree graphs
• Statistics
• Geometric Theorem
• Aspect Ratio
• Proof Of Theorem
• Diamond
• Shortest Path
• Constant Factor
• Line Segment
• Broad-leaved
• Linear Time
• Convex Hull
• Brute Force
• Object Boundaries
• Number Of Squares
• Delaunay Triangulation
• Constant Fraction
• Convex Objective
• Planar Graphs
• Half-angle
• Cluster Diameter