NDLI: Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Please wait, while we are loading the content...

Counting and Enumerating Crossing-free Geometric Graphs

A Framework for Computing the Greedy Spanner

There are Plane Spanners of Maximum Degree 4

New and Improved Spanning Ratios for Yao Graphs

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Progressive Geometric Algorithms

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp

The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems

Design of 3D printed mathematical art

Embeddability in the 3-sphere is decidable

The Connect-The-Dots Family of Puzzles: The Video

LiveCG: an Interactive Visualization Environment for Computational Geometry

Trajectory Grouping Structure: the Video

Visualizing hyperbolic Voronoi diagrams

Animation of an Algorithm for Drawing Graphs in 3D

Visualization of Floater and Gotsman's Morphing Algorithm

Geometric kth Shortest Paths: the Applet

Polytope Offsets and Straight Skeletons in 3D

Optimal Geometric Flows via Dual Programs

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

Outerstring graphs are χ-bounded

Improved bounds for the conflict-free chromatic art gallery problem

Linear transformation distance for bichromatic matchings

Delaunay triangulations with disconnected realization spaces

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

Higher Dimensional Cheeger Inequalities

Incidences between points and lines in R4: Extended Abstract

On triple intersections of three families of unit circles

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Smallest enclosing ball for probabilistic data

Peeling Potatoes Near-Optimally in Near-Linear Time

On the Complexity of Randomly Weighted Voronoi Diagrams

A Census of Plane Graphs with Polyline Edges

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

Using Convex Relaxations for Efficiently and Privately Releasing Marginals

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Better embeddings for planar Earth-Mover Distance over sparse sets

Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement

On the reconstruction of convex sets from random normal measurements

Intersection of paraboloids and application to Minkowski-type problems

Efficient Random-Walk Methods for Approximating Polytope Volume

The Persistent Homology of Distance Functions under Random Projection

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Computing Topological Persistence for Simplicial Maps

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Towards Expressive 3D Modeling: new challenges for geometric computing

Computing the Fréchet distance with shortcuts is NP-hard

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Light spanners for Snowflake Metrics

Continuously Flattening Polyhedra Using Straight Skeletons

Two-Point L1 Shortest Path Queries in the Plane

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Free Edge Lengths in Plane Graphs

Weight Balancing on Boundaries and Skeletons

Separation by Convex Pseudo-Circles

Euclidean Steiner Shallow-Light Trees

Measuring Distance between Reeb Graphs

Stochastic Convergence of Persistence Landscapes and Silhouettes

The Morse Theory of Čech and Delaunay Filtrations

Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

Metric Embedding, Hyperbolic Space, and Social Networks

Sampling with Removal in LP-type Problems

Liftings and stresses for planar periodic frameworks

The Opaque Square

The JS-graphs of Join and Split Trees

Distinct distances on algebraic curves in the plane

Lower bounds on geometric Ramsey functions

Curves in Rd intersecting every hyperplane at most d + 1 times

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Content Provider	ACM Digital Library
Author	Chan, Timothy M. Arya, Sunil
Abstract	Recently, Arya, da Fonseca, and Mount [STOC 2011, SODA 2012] made notable progress in improving the &epsis;-dependencies in the space/query-time tradeoffs for (1 + &epsis;)-factor approximate nearest neighbor search in fixed-dimensional Euclidean spaces. However, &epsis;-dependencies in the preprocessing time were not considered, and so their data structures cannot be used to derive faster algorithms for offline proximity problems. Known algorithms for many such problems, including approximate bichromatic closest pair (BCP) and approximate Euclidean minimum spanning trees (EMST), typically have factors near (1/&epsis;)d/2±O(1) in the running time when the dimension d is a constant. We describe a technique that breaks the (1/&epsis;)d/2 barrier and yields new results for many well-known proximity problems, including: • an O((1/&epsis;)d/3+O(1) n)-time randomized algorithm for approximate BCP, • an O((1/&epsis;)d/3+O(1) n log n)-time algorithm for approximate EMST, and • an O(n log n + (1/&epsis;)d/3+O(1) n)-time algorithm to answer n approximate nearest neighbor queries on n points. Using additional bit-packing tricks, we can shave off the log n factor for EMST, and even move most of the &epsis;-factors to a sublinear term. The improvement arises from a new time bound for exact "discrete Voronoi diagrams", which were previously used in the construction of &epsis;-kernels (or extent-based coresets), a well-known tool for another class of fundamental problems. This connection leads to more results, including: • a streaming algorithm to maintain an approximate diameter in O((1/&epsis;)d/3+O(1)) time per point using O((1/&epsis;)d/2+O(1)) space, and • a streaming algorithm to maintain an &epsis;-kernel in O((1/&epsis;)d/4+O(1)) time per point using O((1/&epsis;)d/2+O(1)) space.
Starting Page	416
Ending Page	425
Page Count	10
File Format	PDF
ISBN	9781450325943
DOI	10.1145/2582112.2582161
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Bichromatic closest pair &epsis;-dependencies Minimum spanning tree Nearest neighbor Coresets
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in