Efficient Colored Orthogonal Range Counting

DOI10.1137/070684483MaRDI QIDQ3631900zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Natan Rubin, Elad Verbin, Micha Sharir

Publication date 22 June 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/070684483

zbMATH Keywords

colored orthogonal range countinggeneralized range searchingmatrix multiplicationoutput-sensitive decompositiontime-space tradeoffunion of orthants

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Combinatorial complexity of geometric structures (52C45) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 6381708
• Colored Range Searching in Linear Space
• Significant-presence range queries in categorical data.
• Approximate range counting revisited
• Approximate range counting revisited

Cited in

(28)

• A box decomposition algorithm to compute the hypervolume indicator
• On the number of maximum empty boxes amidst \(n\) points
• Efficient computation of the search region in multi-objective optimization
• Data structures for categorical path counting queries
• Variations of largest rectangle recognition amidst a bichromatic point set
• Representing the nondominated set in multi-objective mixed-integer programs
• Near-linear approximation algorithms for geometric hitting sets
• Colored top-\(K\) range-aggregate queries
• Counting Colours in Compressed Strings
• Indexing and querying color sets of images
• Colored Range Searching in Linear Space
• On the representation of the search region in multi-objective optimization
• Colored range queries and document retrieval
• Counting patterns in colored orthogonal arrays
• A note about weak -nets for axis-parallel boxes in d-space
• Approximate range counting revisited
• Tight lower bounds for the size of epsilon-nets
• Monomial Tropical Cones for Multicriteria Optimization
• Indexed geometric jumbled pattern matching
• Maximal empty boxes amidst random points
• scientific article; zbMATH DE number 7760157 (Why is no real title available?)
• scientific article; zbMATH DE number 7740901 (Why is no real title available?)
• Adaptive data structures for 2D dominance colored range counting
• On approximate colored path counting
• Hierarchical categories in colored searching
• A simple, efficient and versatile objective space algorithm for multiobjective integer programming
• Faster path queries in colored trees via sparse matrix multiplication and min-plus product
• An output-sensitive algorithm for computing the union of cubes and fat boxes in 3D

This page was built for publication: Efficient Colored Orthogonal Range Counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3631900)