scientific article
From MaRDI portal
Publication:3358267
zbMath0732.68102MaRDI QIDQ3358267
Neil Sarnak, Robert Endre Tarjan
Publication date: 1989
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items (37)
Finding the k smallest spanning trees ⋮ Graphics in flatland revisited ⋮ Space-sweep algorithms for parametric optimization ⋮ Selection in monotone matrices and computing k th nearest neighbors ⋮ Triangles in space or building (and analyzing) castles in the air ⋮ Motion planning in the presence of movable obstacles ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Space–Query-Time Tradeoff for Computing the Visibility Polygon ⋮ Connected component and simple polygon intersection searching ⋮ The inverse Voronoi problem in graphs. II: Trees ⋮ Nearest-neighbor searching under uncertainty. I ⋮ A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane ⋮ Space-efficient functional offline-partially-persistent trees with applications to planar point location ⋮ Constructing Voronoi diagrams from hollow spheres using conformal geometric algebra ⋮ Random access in persistent strings and segment selection ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles ⋮ Zip-zip trees: making zip trees more balanced, biased, compact, or persistent ⋮ Using persistent data structures for adding range restrictions to searching problems ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ New upper bounds for generalized intersection searching problems ⋮ Max-throughput for (conservative) \(k\)-of-\(n\) testing ⋮ Finding the \(k\) smallest spanning trees ⋮ Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time. ⋮ Confluently persistent tries for efficient version control ⋮ Two-dimensional packet classification and filter conflict resolution in the internet ⋮ Unnamed Item ⋮ Dynamic planar point location with optimal query time ⋮ External memory planar point location with logarithmic updates ⋮ Worst-case versus average case complexity of ray-shooting ⋮ Casting an object with a core ⋮ Some Results for Elementary Operations ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ VARIANTS OF (A,B)-TREES WITH RELAXED BALANCE ⋮ New Bounds for Range Closest-Pair Problems ⋮ Adaptive Planar Point Location ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item
This page was built for publication:
