Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
From MaRDI portal
Publication:728495
DOI10.1007/s00454-016-9784-4zbMath1355.68279OpenAlexW2282988760MaRDI QIDQ728495
Timothy M. Chan, Konstantinos Tsakalidis
Publication date: 20 December 2016
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5135/
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)
Related Items
Minimum cuts in geometric intersection graphs, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, Incremental Voronoi diagrams, Dynamic data structures for \(k\)-nearest neighbor queries, Bottleneck matching in the plane, Dynamic connectivity in disk graphs, Unnamed Item, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Dynamic geometric data structures via shallow cuttings, Optimal deterministic shallow cuttings for 3-d dominance ranges, Unnamed Item, Two approaches to building time-windowed geometric data structures, Optimal Algorithms for Geometric Centers and Depth, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Construction of \(\epsilon\)-nets
- Planar separators and parallel polygon triangulation.
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- Reporting points in halfspaces
- Cutting hyperplanes for divide-and-conquer
- On constants for cuttings in the plane
- On levels in arrangements of lines, segments, planes, and triangles
- New applications of random sampling in computational geometry
- Linear Time Algorithms for Two- and Three-Variable Linear Programs
- Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
- A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- Linear Programming in Linear Time When the Dimension Is Fixed
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
- Low-Dimensional Linear Programming with Violations
- Deterministic algorithms for 3-D diameter and some 2-D lower envelopes
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges
- Orthogonal range searching on the RAM, revisited
