Reporting points in halfspaces

From MaRDI portal
Publication:1196295

DOI10.1016/0925-7721(92)90006-EzbMath0772.68105MaRDI QIDQ1196295

Ji{ří} Matoušek

Publication date: 16 December 1992

Published in: Computational Geometry (Search for Journal in Brave)




Related Items (58)

On range searching with semialgebraic setsOn lines missing polyhedral sets in 3-spaceOptimal Encodings for Range Top-$$k$$, Selection, and Min-MaxDynamic half-space range reporting and its applicationsTopology B-trees and their applicationsAlgorithms for polytope covering and approximationAPPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUSAlmost optimal set covers in finite VC-dimensionKinetic sorting and kinetic convex hullsPoint location in zones of \(k\)-flats in arrangementsOn nearest-neighbor graphsNearest-neighbor searching under uncertainty. IDynamic data structures for \(k\)-nearest neighbor queriesGeometric pattern matching in d-dimensional spaceOptimal partition treesApproximate Polytope Membership QueriesRange minima queries with respect to a random permutation, and approximate range countingNear-linear approximation algorithms for geometric hitting setsRelative \((p,\varepsilon )\)-approximations in geometrySimplex Range Searching and Its Variants: A ReviewApproximating the k-Level in Three-Dimensional Plane ArrangementsDynamic planar Voronoi diagrams for general distance functions and their algorithmic applicationsApproximation algorithms for maximum independent set of pseudo-disksOn Dominance Reporting in 3DDynamic geometric data structures via shallow cuttingsA non-linear lower bound for planar epsilon-netsRange closest-pair search in higher dimensionsOn ray shooting in convex polytopesOn approximate range counting and depthOptimal deterministic shallow cuttings for 3-d dominance ranges\(\varepsilon\)-Mnets: Hitting geometric set systems with subsetsTight lower bounds for the size of epsilon-netsApproximate range searching: The absolute modelRay shooting and stone throwing with near-linear storageUnnamed ItemON ENUMERATING AND SELECTING DISTANCESUnnamed ItemUnnamed ItemA general approach for cache-oblivious range reporting and approximate range countingOptimal deterministic algorithms for 2-d and 3-d shallow cuttingsTwo proofs for shallow packingsComputing coverage kernels under restricted settingsNear-linear algorithms for geometric hitting sets and set coversUnnamed ItemSmallest \(k\)-enclosing rectangle revisitedUnnamed ItemSmallest k-enclosing rectangle revisitedDynamic ham-sandwich cuts in the planeFaster DBSCAN and HDBSCAN in Low-Dimensional Euclidean SpacesA (slightly) faster algorithm for Klee's measure problemSuccinct and Implicit Data Structures for Computational GeometryEconomical Delone Sets for Approximating Convex BodiesExtremal point queries with lines and line segments and related problemsEfficient searching with linear constraintsUnnamed ItemOptimal Algorithms for Geometric Centers and DepthNearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance FunctionsFaster DBScan and HDBScan in Low-Dimensional Euclidean Spaces



Cites Work


This page was built for publication: Reporting points in halfspaces