Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

DOI10.4230/LIPIcs.SOCG.2015.719zbMath1378.68165OpenAlexW2296549964MaRDI QIDQ5368723

Timothy M. Chan, Konstantinos Tsakalidis

Publication date: 10 October 2017

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2015/5135/pdf/52.pdf/

zbMATH Keywords

derandomizationgeometric data structureshalfspace range reportingshallow cuttings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Related Items (8)

A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ Affine invariants of generalized polygons and matching under affine transformations ⋮ Spanners for Directed Transmission Graphs ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Unnamed Item

This page was built for publication: Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings