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

DOI10.4230/LIPICS.SOCG.2015.719MaRDI QIDQ5368723zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Optimal deterministic shallow cuttings for 3D dominance ranges
• Optimal deterministic shallow cuttings for 3-d dominance ranges
• Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study
• A recursive algorithm for constrained two-dimensional cutting problems
• scientific article; zbMATH DE number 4133833
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Approximation algorithms for feasible cut and multicut problems
• An optimal algorithm for the minimum edge cardinality cut surface problem
• A recursive exact algorithm for weighted two-dimensional cutting

Cited in

(13)

• Optimal deterministic shallow cuttings for 3-d dominance ranges
• Near-linear algorithms for geometric hitting sets and set covers
• 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
• 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
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Optimal deterministic shallow cuttings for 3D dominance ranges
• Algorithm 825
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings

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 Q5368723)