Construction of \(\epsilon\)-nets
From MaRDI portal
Publication:914376
DOI10.1007/BF02187804zbMath0701.68040OpenAlexW307932172MaRDI QIDQ914376
Publication date: 1990
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131131
combinatorial geometryapproximate partitioning of intersectionscomputational complexity of \(\epsilon\)-netscutting line arrangements
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)
Related Items
Corrigendum to: ``On disjoint concave chains in arrangements of (pseudo) lines, Algorithms for ham-sandwich cuts, On lines missing polyhedral sets in 3-space, A survey of mass partitions, Almost optimal set covers in finite VC-dimension, The common exterior of convex polygons in the plane, Lines in space: Combinatorics and algorithms, Space–Query-Time Tradeoff for Computing the Visibility Polygon, A center transversal theorem for hyperplanes and applications to graph drawing, Relative \((p,\varepsilon )\)-approximations in geometry, Simplex Range Searching and Its Variants: A Review, Approximating the k-Level in Three-Dimensional Plane Arrangements, Ham-sandwich cuts for abstract order types, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Partitioning arrangements of lines. II: Applications, Cutting hyperplane arrangements, On disjoint concave chains in arrangements of (pseudo) lines, The number of edges of many faces in a line segment arrangement, Cutting hyperplanes for divide-and-conquer, Optimal deterministic algorithms for 2-d and 3-d shallow cuttings, Extending the centerpoint theorem to multiple points
Cites Work
- Unnamed Item
- Unnamed Item
- Sorting in \(c \log n\) parallel steps
- More on k-sets of finite sets in the plane
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- On the ratio of optimal integral and fractional covers
- Implicitly representing arrangements of lines or segments
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- A linear time algorithm for minimum link paths inside a simple polygon
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- An Optimal-Time Algorithm for Slope Selection
- A Greedy Heuristic for the Set-Covering Problem
- Slowing down sorting networks to obtain faster sorting algorithms
- Constructing Belts in Two-Dimensional Arrangements with Applications
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
