Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
From MaRDI portal
Recommendations
Cites work
- -nets and simplex range queries
- A deterministic view of random sampling and its use in geometry
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- A Separator Theorem for Planar Graphs
- Construction of \(\epsilon\)-nets
- Cutting hyperplane arrangements
- Cutting hyperplanes for divide-and-conquer
- Deterministic algorithms for 3-D diameter and some 2-D lower envelopes
- Deterministic rectangle enclosure and offline dominance reporting on the RAM
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- scientific article; zbMATH DE number 1617248 (Why is no real title available?)
- scientific article; zbMATH DE number 49092 (Why is no real title available?)
- Linear Programming in Linear Time When the Dimension Is Fixed
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
- Low-Dimensional Linear Programming with Violations
- New applications of random sampling in computational geometry
- On constants for cuttings in the plane
- On levels in arrangements of lines, segments, planes, and triangles
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal deterministic shallow cuttings for 3D dominance ranges
- Optimal halfspace range reporting in three dimensions
- Orthogonal range searching on the RAM, revisited
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Planar separators and parallel polygon triangulation.
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase(\le k)-Levels in Three Dimensions
- Reporting points in halfspaces
- Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
Cited in
(30)- Incremental Voronoi diagrams
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Dynamic geometric data structures via shallow cuttings
- Two approaches to building time-windowed geometric data structures
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- scientific article; zbMATH DE number 4133833 (Why is no real title available?)
- Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids
- scientific article; zbMATH DE number 7559224 (Why is no real title available?)
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal deterministic shallow cuttings for 3D dominance ranges
- Algorithm 825
- Optimal algorithms for geometric centers and depth
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- scientific article; zbMATH DE number 7651184 (Why is no real title available?)
- Dynamic data structures for \(k\)-nearest neighbor queries
- Bottleneck matching in the plane
- Dynamic connectivity in disk graphs
- Linear expected complexity for directional and multiplicative Voronoi diagrams
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- Sparsifying disk intersection graphs for reliable connectivity
- More dynamic data structures for geometric set cover with sublinear update time
- Lower envelopes of surface patches in 3-space
- Robust classification of dynamic bichromatic point sets in \(\mathbb{R}^2\)
- Dynamic unit-disk range reporting
- Maximizing the optimality streak of deferred data structuring (a.k.a. database cracking)
- Convexity helps iterated search in 3D
- Higher-order color Voronoi diagrams and the colorful Clarkson-Shor framework
- Incremental planar nearest neighbor queries with optimal query time
- Minimum cuts in geometric intersection graphs
This page was built for publication: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q728495)
