2002/11/27 by Warren D. Smith, N. C. Wormald · 7 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Smart Parking Systems Research
paper · doi:10.1109/sfcs.1998.743449
openalex publication_date 2002/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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".