On the power of the semi-separated pair decomposition
From MaRDI portal
Publication:1947974
DOI10.1016/j.comgeo.2013.02.003zbMath1264.65022OpenAlexW2102958968MaRDI QIDQ1947974
Mohammad Ali Abam, Mohammad Farshi, Paz Carmi, Michiel H. M. Smid
Publication date: 29 April 2013
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.02.003
algorithmcomputational geometrysemi-separated pair decompositionclosest-pair queryimprecise spannersspanners for complete \(k\)-partite graphs
Related Items (8)
Closest-pair queries and minimum-weight queries are equivalent for squares ⋮ New bounds for range closest-pair problems ⋮ On algorithmic complexity of imprecise spanners ⋮ Approximate range closest-pair queries ⋮ Spanners for geodesic graphs and visibility graphs ⋮ Range closest-pair search in higher dimensions ⋮ Finding pairwise intersections inside a query range ⋮ Closest-pair queries in fat rectangles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Data structures for range-aggregate extent queries
- New constructions of SSPDs and their applications
- Optimal partition trees
- Ordered theta graphs
- Geometric spanners for weighted point sets
- On separating systems
- Approximating largest convex hulls for imprecise points
- Region-fault tolerant geometric spanners
- Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
- Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Geometric Spanner Networks
- Delaunay triangulations of imprecise pointsin linear time after preprocessing
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Spanners of Complete k-Partite Geometric Graphs
This page was built for publication: On the power of the semi-separated pair decomposition
