NDLI: Orthogonal range searching on the RAM, revisited

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

Orthogonal range searching on the RAM, revisited

Metric graph reconstruction from noisy data

Can they cross? and how?: (the hitchhiker's guide to the universe of geometric intersection graphs)

Exploiting temporal coherence in forest dynamics simulation

A kuratowski-type theorem for planarity of partially embedded graphs

The least spanning area of a knot and the optimal bounding chain problem

Theoretical and practical results on straight skeletons of planar straight-line graphs

An output-sensitive algorithm for persistent homology

Kinetic convex hulls and delaunay triangulations in the black-box model

Redelmeier's algorithm for counting lattice animals

Answering geographic questions with user generated content: experiences from the coal face

Integer representations of convex polygon intersection graphs

Beating the spread: time-optimal point meshing

Minors in random and expanding hypergraphs

Guarding polyominoes

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Tight lower bounds for the size of epsilon-nets

Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes

Convex hull of imprecise points in o(n log n) time after preprocessing

Comparing distributions and shapes using the kernel distance

Compressive sensing with local geometric features

A center transversal theorem for hyperplanes and applications to graph drawing

A tree traversal algorithm for decision problems in knot theory and 3-manifold topology

A generic algebraic kernel for non-linear geometric applications

Zigzag persistent homology in matrix multiplication time

The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites

Geometric computation with smart pixels

Sphere and dot product representations of graphs

Edge flips and deforming surface meshes

Bounds on the complexity of halfspace intersections when the bounded faces have small dimension

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

On the euclidean bottleneck full Steiner tree problem

No dimension independent core-sets for containment under homothetics

Efficient data structure for representing and simplifying simplicial complexes in high dimensions

A static optimality transformation with applications to planar point location

Witnessed k-distance

Persistence-based clustering in riemannian manifolds

Disjoint compatible geometric matchings

The pachner graph and the simplification of 3-sphere triangulations

Deconstructing approximate offsets

Reeb graphs: approximation and persistence

Improved upper bound on the stretch factor of delaunay triangulations

Ant-sweep: a decentral strategy for cooperative cleaning in expanding domains

Contact representations of planar graphs with cubes

Kinetic mesh refinement in 2D

On the structure and composition of forbidden sequences, with geometric applications

Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons

The euclidean bottleneck steiner path problem

Extremal reaches in polynomial time

Boundary of a non-uniform point cloud for reconstruction: extended abstract

Three problems about dynamic convex hulls

Stochastic minimum spanning trees in euclidean spaces

Space crossing numbers

Stable snap rounding

Shortest non-trivial cycles in directed surface graphs

Delaunay triangulations of point sets in closed euclidean d-manifolds

Visualization of discrete gradient construction

A new upper bound for the VC-dimension of visibility regions

Covering cubes and the closest vector problem

The frechet distance revisited and extended

Exact workspace boundary by extremal reaches

Fitting spheres to electron density

Minimum perimeter convex hull of imprecise points in convex regions

A pedagogic JavaScript program for point location strategies

Orthogonal range searching on the RAM, revisited

Content Provider	ACM Digital Library
Author	Larsen, Kasper Green Chan, Timothy M. Pătraşcu, Mihai
Abstract	We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lg lg n) space and O(lg lg n) query time, assuming that the n given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with O(n $lg^{ε}$ n) space and O(lg lg n) query time, or with O(n lg lg n) space and $O(lg^{2}lg$ n) query time. Our second data structure uses O(n) space and answers queries in $O(lg^{ε}$ n) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lg n/lg lg n) time. We give a data structure for 3-d orthogonal range reporting with O(n $lg^{1+ε}$ n) space and O(lg lg n + k) query time for points in rank space, for any constant ε>0. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n $lg^{3}$ n) space and O(lg lg n + k) query time, or with O(n $lg^{1+ε}n)$ space and $O(lg^{2}lg$ n + k) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3. Our approach also leads to a new data structure for 2D orthogonal range minimum queries with O(n $lg^{ε}$ n) space and O(lg lg n) query time for points in rank space. We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(n log n) plus the output size. This resolves two open problems (both appeared in Preparata and Shamos' seminal book): given a set of n axis-aligned rectangles in the plane, we can report all k enclosure pairs (i.e., pairs $(r_{1},r_{2})$ where rectangle $r_{1}$ completely encloses rectangle $r_{2})$ in O(n lg n + k) expected time; given a set of n points in 4-d, we can find all maximal points (points not dominated by any other points) in O(n lg n) expected time. The most recent previous development on (a) was reported back in SoCG'95 by Gupta, Janardan, Smid, and Dasgupta, whose main result was an O([n lg n + k] lg lg n) algorithm. The best previous result on (b) was an O(n lg n lg lg n) algorithm due to Gabow, Bentley, and Tarjan---from STOC'84! As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above~4.
Starting Page	1
Ending Page	10
Page Count	10
File Format	PDF
ISBN	9781450306829
DOI	10.1145/1998196.1998198
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Geometric data structures Dominance Word ram Maxima Orthogonal range searching
Content Type	Text
Resource Type	Article

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

Fully Dynamic Orthogonal Range Reporting on RAM

Orthogonal range searching on the ram, revisited (2011).

M.: Orthogonal range searching on the ram, revisited (2011)

Orthogonal Range Searching on the RAM, Revisited

Cache-oblivious data structures for orthogonal range searching

Space efficient dynamic orthogonal range reporting

Optimal partition trees

A dynamic data structure for approximate range searching

Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching

Orthogonal range searching on the RAM, revisited

Similar Documents

Fully Dynamic Orthogonal Range Reporting on RAM

Orthogonal range searching on the ram, revisited (2011).

M.: Orthogonal range searching on the ram, revisited (2011)

Orthogonal Range Searching on the RAM, Revisited

Cache-oblivious data structures for orthogonal range searching

Space efficient dynamic orthogonal range reporting

Optimal partition trees

A dynamic data structure for approximate range searching

Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching

Orthogonal range searching on the RAM, revisited