On the power of the semi-separated pair decomposition

DOI10.1016/j.comgeo.2013.02.003zbMath1264.65022MaRDI 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

zbMATH Keywords

algorithm; computational geometry; semi-separated pair decomposition; closest-pair query; imprecise spanners; spanners for complete \(k\)-partite graphs

Mathematics Subject Classification ID

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Range closest-pair search in higher dimensions, Spanners for geodesic graphs and visibility graphs, Finding pairwise intersections inside a query range, Approximate range closest-pair queries, 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