Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.

No abstract is available for this paper.

• Publication year

  1998

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers

  No identifiers available.

• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Taking a walk in a planar arrangement

  1999cited by this paper
• Remarks on k-Level Algorithms in the Plane

  1999cited by this paper
• On range reporting, ray shooting and k-level construction

  1999cited by this paper
• Dynamic planar convex hull operations in near-logarithmic amortized time

  1999cited by this paper
• Topological Walk Revisited

  1998cited by this paper
• On enumerating and selecting distances

  1998cited by this paper
• On Levels in Arrangements of Lines, Segments, Planes, and Triangles%

  1997influential reference
• Improved bounds on planar k-sets and k-levels

  1997influential reference
• K-sets and j-facets - A tour of discrete geometry

  1997cited by this paper
• In handbook of discrete and computational geometry

  1997cited by this paper
• Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications

  1995cited by this paper
• Output-sensitive results on convex hulls, extreme points, and related problems

  1995cited by this paper
• Geometric range searching

  1994cited by this paper
• Computing many faces in arrangements of lines and segments

  1994cited by this paper
• Constructing levels in arrangements and higher order Voronoi diagrams

  1994influential reference
• An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problems

  1993cited by this paper
• Computational geometry - an introduction through randomized algorithms

  1993influential reference
• An optimal convex hull algorithm in any fixed dimension

  1993cited by this paper
• Counting triangle crossings and halving planes

  1993cited by this paper
• Reporting Points in Halfspaces

  1992cited by this paper
• Ray shooting and parametric search

  1992cited by this paper
• Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the plane

  1992cited by this paper
• Voronoi diagrams—a survey of a fundamental geometric data structure

  1991cited by this paper
• A general approach to removing degeneracies

  1991cited by this paper
• A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams

  1991cited by this paper
• On levels in arrangements and voronoi diagrams

  1991cited by this paper
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1990cited by this paper
• Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k

  1990cited by this paper
• Solving query-retrieval problems by compacting Voronoi diagrams

  1990cited by this paper
• A Randomized Algorithm for Closest-Point Queries

  1988influential reference
• Applications of random sampling in computational geometry, II

  1988influential reference
• A deterministic view of random sampling and its use in geometry

  1988influential reference
• New applications of random sampling in computational geometry

  1987cited by this paper
• A linear-time algorithm for computing the voronoi diagram of a convex polygon

  1987influential reference
• Algorithms in Combinatorial Geometry

  1987influential reference
• Constructing Belts in Two-Dimensional Arrangements with Applications

  1986influential reference
• Halfspace range search: an algorithmic application of K-sets

  1985cited by this paper
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

  1985influential reference
• On the convex layers of a planar set

  1985cited by this paper
• On k-hulls and related problems

  1984cited by this paper
• Filtering search: A new approach to query-answering

  1983cited by this paper
• The power of geometric duality

  1983influential reference
• Constructing arrangements of lines and hyperplanes with applications

  1983cited by this paper
• On k-Nearest Neighbor Voronoi Diagrams in the Plane

  1982cited by this paper
• A Note on Euclidean Near Neighbor Searching in the Plane

  1979cited by this paper
• Closest-point problems

  1975cited by this paper
• Dissection Graphs of Planar Point Sets

  1973cited by this paper

• Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

  2025cites this paper
• Convexity Helps Iterated Search in 3D

  2025cites this paper
• Dynamic Unit-Disk Range Reporting

  2024influential citation
• Computing k-Crossing Visibility through k-levels

  2023influential citation
• Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size

  2023cites this paper
• An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

  2023influential citation
• Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing

  2022cites this paper
• Does Preprocessing Help Training Over-parameterized Neural Networks?

  2021cites this paper
• On the Number of Incidences when Avoiding the Klan

  2021cites this paper
• (Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems

  2021influential citation
• More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

  2021cites this paper
• On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings

  2021influential citation
• Dynamic Data Structures for k-Nearest Neighbor Queries

  2021cites this paper
• Further Results on Colored Range Searching

  2020cites this paper
• Faster Approximation Algorithms for Geometric Set Cover

  2020cites this paper
• Independent Range Sampling, Revisited Again

  2019cites this paper
• Fast Algorithms for Geometric Consensuses

  2019cites this paper
• Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon

  2018influential citation
• An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams

  2018cites this paper
• On k Nearest Neighbor Queries in the Plane for General Distance Functions

  2018cites this paper
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions

  2018influential citation
• Simplex Range Searching and Its Variants: A Review

  2017cites this paper
• Improved Time-Space Trade-offs for Computing Voronoi Diagrams

  2017cites this paper
• Independent Range Sampling, Revisited

  2017cites this paper
• 28 Arrangements

  2016cites this paper
• Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications

  2016cites this paper
• Approximating the $k$-Level in Three-Dimensional Plane Arrangements

  2016cites this paper
• Instance Optimal Geometric Algorithms

  2015cites this paper
• Approximate Range Counting Revisited

  2015cites this paper
• 2 Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings 1 . 1 Standard Cuttings

  2015cites this paper
• The k-Nearest-Neighbor Voronoi Diagram Revisited

  2015cites this paper
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

  2015cites this paper
• Tessellations for Geometric Optimization

  2015cites this paper
• Approximating the Simplicial Depth

  2015cites this paper
• Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges

  2014cites this paper
• The Higher-Order Voronoi Diagram of Line Segments

  2014cites this paper
• A Unified Framework for Efficiently Processing Ranking Related Queries

  2014cites this paper
• Bottleneck partial-matching Voronoi diagrams and applications

  2014cites this paper
• Higher-order Voronoi diagrams of polygonal objects

  2014cites this paper
• A Sweepline Algorithm for Higher Order Voronoi Diagrams

  2013cites this paper
• A dynamic I/O-efficient structure for one-dimensional top-k range reporting

  2012cites this paper
• On Top-k Search and Range Reporting

  2012cites this paper
• Minimizing the error of linear separators on linearly inseparable data

  2012cites this paper
• RANGE SEARCHING DATA STRUCTURES WITH CACHE LOCALITY

  2011cites this paper
• Centroid Triangulations from k-Sets

  2011cites this paper
• Improved space bounds for cache-oblivious range reporting

  2011cites this paper
• Relative (p,ε)-Approximations in Geometry

  2011cites this paper
• Convex hull of imprecise points in o(n log n) time after preprocessing

  2011cites this paper
• Three problems about dynamic convex hulls

  2011cites this paper
• Convex hull of points lying on lines in time after preprocessing

  2011cites this paper
• Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting

  2011cites this paper
• Low-Entropy Computational Geometry

  2010cites this paper
• Ja n 20 10 Relative ( p , ε )-Approximations in Geometry ∗

  2010cites this paper
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries

  2010influential citation
• Relative (p,epsilon)-Approximations in Geometry

  2009cites this paper
• Instance-Optimal Geometric Algorithms

  2009cites this paper
• A general approach for cache-oblivious range reporting and approximate range counting

  2009cites this paper
• Cache-Oblivious Range Reporting with Optimal Queries Requires Superlinear Space

  2009cites this paper
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time

  2009influential citation
• Optimal halfspace range reporting in three dimensions

  2009influential citation
• Indexing uncertain data

  2009cites this paper
• Measuring the error of linear separators on linearly inseparable data

  2009cites this paper
• Constructing minimum-interference networks

  2008cites this paper
• Computing closest and farthest points for a query segment

  2008cites this paper
• On Geometric Range Searching, Approximate Counting and Depth Problems

  2008cites this paper
• Construction and Analysis of Geometric Networks

  2007cites this paper
• On Approximate Range Counting and Depth

  2007influential citation
• Computational geometry through the information lens

  2007cites this paper
• Computational Geometry through the Information Lens by Mihai Pǎtraşcu

  2007cites this paper
• Point Location in Time, Voronoi Diagrams in Time, and Other Transdichotomous Results in Computational Geometry

  2006cites this paper
• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries

  2006cites this paper
• Relative ε-Approximations in Geometry ∗

  2006cites this paper
• Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting

  2006cites this paper
• Fast Approximation of High Order Voronoi Diagrams and Distance Transforms on the GPU

  2006cites this paper
• Constructing interference-minimal networks

  2006cites this paper
• Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU

  2006cites this paper
• On approximating the depth and related problems

  2005cites this paper
• Constructing higher-order Voronoi diagrams in parallel

  2005cites this paper
• Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

  2004cites this paper
• Algorithms for Memory Hierarchies

  2003cites this paper
• Lectures on discrete geometry

  2002cites this paper
• Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D

  2002cites this paper
• Low-dimensional linear programming with violations

  2002cites this paper
• External Memory Data Structures

  2001cites this paper
• External Memory Data Structures (invited Paper)

  2001cites this paper
• Approximation algorithms for layered manufacturing

  2000cites this paper
• On range reporting, ray shooting and k-level construction

  1999cites this paper
• Dynamic planar convex hull operations in near-logarithmic amortized time

  1999cites this paper
• Efficient Searching with Linear Constraints 1

  1999influential citation
• On enumerating and selecting distances

  1998cites this paper
• cient Searching with Linear Constraints

  year unknowncites this paper