Cutting hyperplanes for divide-and-conquer

DOI10.1007/BF02189314zbMath0784.52018MaRDI QIDQ1209837

Publication date: 16 May 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131240

zbMATH Keywords

linear programming simplex computational geometry cutting hyperplane arrangement deterministic algorithm point location epsilon-net segment intersection divide- and-conquer line/point incidence

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Linear programming (90C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items

On counting point-hyperplane incidences, On range searching with semialgebraic sets, Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, A semi-algebraic version of Zarankiewicz's problem, FITTING A STEP FUNCTION TO A POINT SET WITH OUTLIERS BASED ON SIMPLICIAL THICKNESS DATA STRUCTURES, REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS, Cuttings for disks and axis-aligned rectangles in three-space, A survey of mass partitions, COMPUTING CLOSEST POINTS FOR SEGMENTS, A note on point location in arrangements of hyperplanes, Almost optimal set covers in finite VC-dimension, Vertical decompositions for triangles in 3-space, A new asymmetric inclusion region for minimum weight triangulation, Space–Query-Time Tradeoff for Computing the Visibility Polygon, Improved upper bounds for approximation by zonotopes, The exact fitting problem in higher dimensions, A deterministic algorithm for the three-dimensional diameter problem, Convex hulls under uncertainty, On fat partitioning, fat covering and the union size of polygons, Optimal slope selection via cuttings, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Decomposable multi-parameter matroid optimization problems., Optimal partition trees, Fast separator decomposition for finite element meshes, Simplex Range Searching and Its Variants: A Review, Approximating the k-Level in Three-Dimensional Plane Arrangements, The 2-center problem in three dimensions, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, An affine invariant \(k\)-nearest neighbor regression estimate, Covering lattice points by subspaces and counting point-hyperplane incidences, FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS, Counting the number of crossings in geometric graphs, Removing depth-order cycles among triangles: an algorithm generating triangular fragments, A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs, Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures, Efficient algorithms for maximum regression depth, Range closest-pair search in higher dimensions, On counting pairs of intersecting segments and off-line triangle range searching, Range searching with efficient hierarchical cuttings, On ray shooting in convex polytopes, Efficient partition trees, Linear-space data structures for range mode query in arrays, Maximum overlap and minimum convex hull of two convex polyhedra under translations, On the number of regular vertices of the union of Jordan regions, An efficient algorithm for the three-dimensional diameter problem, Computing the center region and its variants, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Approximate input sensitive algorithms for point pattern matching, Planar point sets determine many pairwise crossing segments, On vertical ray shooting in arrangements, Robust shape fitting via peeling and grating coresets, Output-sensitive results on convex hulls, extreme points, and related problems, New lower bounds for Hopcroft's problem, On range searching with semialgebraic sets, Clamshell casting, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Subquadratic Encodings for Point Configurations, Approximating the packedness of polygonal curves, An optimal convex hull algorithm in any fixed dimension, Optimal Algorithms for Geometric Centers and Depth, Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems, Algorithms for bichromatic line-segment problems and polyhedral terrains, Reporting intersecting pairs of convex polytopes in two and three dimensions, Weak visibility counting in simple polygons, IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS, Stability versus speed in a computable algebraic model

Cites Work