Relative (p,ε)-Approximations in Geometry

No abstract is available for this paper.

• Publication year

  2011

• Venue

  Discrete & Computational Geometry

• Publication date

  2011-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-010-9248-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting

  2011cited by this paper
• Yet even more on sampling

  2011cited by this paper
• The Overlay of Minimization Diagrams in a Randomized Incremental Construction

  2011cited by this paper
• Approximate Halfspace Range Counting

  2010cited by this paper
• Carnival of Samplings: Nets, Approximations, Relative and Sensitive

  2009cited by this paper
• Relative (p,epsilon)-Approximations in Geometry

  2009cited by this paper
• Semialgebraic Range Reporting and Emptiness Searching with Applications

  2009cited by this paper
• On Approximate Range Counting and Depth

  2007influential reference
• Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry

  2007cited by this paper
• Using The Borsuk-Ulam Theorem

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

  2006cited by this paper
• Combinatorial Geometry

  2006cited by this paper
• On approximating the depth and related problems

  2005cited by this paper
• The discrepancy method in computational geometry

  2004cited by this paper
• Dynamic planar convex hull

  2002cited by this paper
• Improved bounds on the sample complexity of learning

  2000influential reference
• On K-sets and Their Generalizations

  2000cited by this paper
• Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.

  1998cited by this paper
• Improved Bounds for Planar k -Sets and Related Problems

  1998cited by this paper
• On levels in arrangements of lines

  1998cited by this paper
• The Discrepancy Method

  1998influential reference
• Results on k-sets and j-facets via continuous motion

  1998cited by this paper
• Regression Depth and Center Points

  1998cited by this paper
• Handbook of Discrete and Computational Geometry, Second Edition

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

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

  1997cited by this paper
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS

  1996cited by this paper
• Derandomization of geometric algorithms

  1995cited by this paper
• Combinatorial geometry

  1995cited by this paper
• Sharper Bounds for Gaussian and Empirical Processes

  1994cited by this paper
• An optimal algorithm for the (≤ k)-levels, with applications to separation and transversal problems

  1993cited by this paper
• Product range spaces, sensitive sampling, and derandomization

  1993influential reference
• Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications

  1992cited by this paper
• Reporting Points in Halfspaces

  1992influential reference
• On Spanning Trees with Low Crossing Numbers

  1992cited by this paper
• Almost tight bounds forɛ-Nets

  1992cited by this paper
• Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative

  1992cited by this paper
• Discrete and Computational Geometry: Papers from the DIMACS Special Year

  1991cited by this paper
• Efficient partition trees

  1991influential reference
• Discrepancy and approximations for bounded VC-dimension

  1991cited by this paper
• Computing the center of planar point sets

  1991cited by this paper
• Construction of ɛ-nets

  1990cited by this paper
• Computing the Center of Planar Point Sets

  1990cited by this paper
• Construction of epsilon nets

  1989cited by this paper
• Quasi-optimal range searching in spaces of finite VC-dimension

  1989cited by this paper
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• New applications of random sampling in computational geometry

  1987cited by this paper
• ɛ-nets and simplex range queries

  1987cited by this paper
• More onk-sets of finite sets in the plane

  1986cited by this paper
• Planar Point Location Using Persistent Search Trees a

  1986cited by this paper
• Epsilon-nets and simplex range queries

  1986cited by this paper
• Optimal Search in Planar Subdivisions

  1983cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper

• A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem

  2025cites this paper
• Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems

  2025cites this paper
• Stable coresets: Unleashing the power of uniform sampling

  2025cites this paper
• A Query-Driven Approach to Space-Efficient Range Searching

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

  2025cites this paper
• Monotone Classification with Relative Approximations

  2025cites this paper
• QCore: Data-Efficient, On-Device Continual Calibration for Quantized Models - Extended Version

  2024cites this paper
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs

  2023influential citation
• Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers

  2023cites this paper
• Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping

  2023influential citation
• Efficient Centrality Maximization with Rademacher Averages

  2023cites this paper
• Fast Approximation Algorithms for Piercing Boxes by Points

  2023cites this paper
• Estimation and update of betweenness centrality with progressive algorithm and shortest paths approximation

  2023cites this paper
• Simplified and Improved Bounds on the VC-Dimension for Elastic Distance Measures

  2023cites this paper
• Approximating Multidimensional Range Counts with Maximum Error Guarantees

  2021cites this paper
• Efficient Coreset Constructions via Sensitivity Sampling

  2021cites this paper
• Percolation centrality via Rademacher Complexity

  2021cites this paper
• Problema APSP via Dimensão-VC e Médias de Rademacher

  2021cites this paper
• Finding an Approximate Mode of a Kernel Density Estimate

  2021cites this paper
• Practical I/O-Efficient Multiway Separators

  2021cites this paper
• Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries

  2021cites this paper
• SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds

  2021cites this paper
• Data-Independent Space Partitionings for Summaries

  2021cites this paper
• TipTap: Approximate Mining of Frequent k-Subgraph Patterns in Evolving Graphs

  2021cites this paper
• Coresets for $(k, \ell)$-Median Clustering under the Fr\'echet Distance

  2021influential citation
• Digital almost nets

  2021cites this paper
• On Ray Shooting for Triangles in 3-Space and Related Problems

  2021cites this paper
• Optimal approximations made easy

  2020cites this paper
• Approximation of Interactive Betweenness Centrality in Large Complex Networks

  2020cites this paper
• New Directions in Streaming Algorithms

  2020influential citation
• Minimum Enclosing Parallelogram with Outliers

  2020influential citation
• Weighted Epsilon-Nets

  2020cites this paper
• Improved Approximation Algorithms for Tverberg Partitions

  2020cites this paper
• Weighted Epsilon-Nets

  2020cites this paper
• Minimum Enclosing Parallelogram with Outliers

  2020cites this paper
• Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments

  2020cites this paper
• Finding the Mode of a Kernel Density Estimate

  2019cites this paper
• Mining Expected Support-Based Frequent Itemsets by Sampling

  2019cites this paper
• Fast top-k similarity search in large dynamic attributed networks

  2019influential citation
• Geometric Crossing-Minimization - A Scalable Randomized Approach

  2019cites this paper
• Algorithmic and geometric aspects of data depth with focus on β-skeleton depth

  2019cites this paper
• Learning to Screen

  2019influential citation
• Algorithmic and geometric aspects of data depth with focus on $\beta$-skeleton depth

  2019cites this paper
• The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances

  2019cites this paper
• Output-Optimal Massively Parallel Algorithms for Similarity Joins

  2019influential citation
• Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction

  2019cites this paper
• Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges

  2019influential citation
• k-Means Clustering of Lines for Big Data

  2019cites this paper
• Smallest k-Enclosing Rectangle Revisited

  2019cites this paper
• Shortest Path Centrality and the APSP problem via VC-dimension and Rademacher Averages

  2019cites this paper
• VizCertify: A Framework for Secure Visual Data Exploration

  2019cites this paper
• Learning and Generalization for Matching Problems

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

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

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

  2018cites this paper
• Approximate Data Depth Revisited

  2018cites this paper
• Tight Space Bounds for Two-Dimensional Approximate Range Counting

  2018cites this paper
• A Simple Proof of Optimal Epsilon Nets

  2018cites this paper
• VizRec: A framework for secure data exploration via visual representation

  2018cites this paper
• An Efficient Algorithm for Minimum Enclosing Ball with Outliers and Application

  2018cites this paper
• Solving Minimum Enclosing Ball with Outliers: Algorithm, Implementation, and Application

  2018cites this paper
• Bi-criteria Approximation Algorithms for Minimum Enclosing Ball and $k$-Center Clustering with Outliers

  2018cites this paper
• ABRA

  2018cites this paper
• NSF Proposal: AF 7435149: Towards better geometric algorithms: Summarizing, partitioning and shrinking data

  2018cites this paper
• Journey to the Center of the Point Set

  2017cites this paper
• How to Net a Convex Shape

  2017cites this paper
• Epsilon-Approximations & Epsilon-Nets

  2017cites this paper
• Output-optimal Parallel Algorithms for Similarity Joins

  2017cites this paper
• Fe b 20 17 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• Link prediction based on sampling in complex networks

  2017cites this paper
• Sublinear algorithms for massive data problems

  2017cites this paper
• Epsilon-approximations and epsilon-nets

  2017influential citation
• A Simple Proof of Optimal Epsilon Nets

  2017cites this paper
• 48 CORESETS AND SKETCHES

  2017cites this paper
• 2 01 7 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2017cites this paper
• Simplex Range Searching and Its Variants: A Review

  2017cites this paper
• Approximate Parallel High Utility Itemset Mining

  2016cites this paper
• Coresets and Sketches

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

  2016cites this paper
• Scalable spatial scan statistics through sampling

  2016cites this paper
• Two Proofs for Shallow Packings

  2016cites this paper
• Covering many points with a small-area box

  2016cites this paper
• 47 EPSILON-APPROXIMATIONS & EPSILON-NETS

  2016cites this paper
• New Frameworks for Offline and Streaming Coreset Constructions

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

  2016influential citation
• Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension

  2016cites this paper
• APPROXIMATE PARALLEL HIGH UTILITY ITEMSET MINING YAN CHEN A THESIS SUBMITTED TO THE FACULTY OF GRADUATE STUDIES IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE GRADUATE PROGRAM IN COMPUTER SCIENCE

  2016cites this paper
• ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages

  2016influential citation
• 44 RANDOMIZATION AND DERANDOMIZATION

  2016cites this paper
• Betweenness centrality in Delay Tolerant Networks: A survey

  2015cites this paper
• Comparison of sampling size estimation techniques for association rule mining

  2015cites this paper
• Approximate Range Counting Revisited

  2015cites this paper
• Towards Tight Bounds for the Streaming Set Cover Problem

  2015influential citation
• Pazar Sepet Analizi için Örneklem Oluşturulması ve Birliktelik Kurallarının Çıkartılması

  2015cites this paper
• Size sensitive packing number for Hamming cube and its consequences

  2014cites this paper
• Shallow Packings in Geometry

  2014influential citation
• Fast approximation of betweenness centrality through sampling

  2014cites this paper
• The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

  2014cites this paper
• Sampling-Based Data Mining Algorithms: Modern Techniques and Case Studies

  2014cites this paper
• Output-Sensitive Tools for Range Searching in Higher Dimensions

  2013cites this paper