General methods for adding range restrictions to decomposable searching problems
The problem of adding range restrictions to decomposable searching problems consists in associating a new parameter with every element of the given set of objects. Thus, queries will be restricted to those objects that have this new parameter in a certain given range. Two classes of structures for this problem are presented. The first class contains structures that have low storage cost at an expense of increased query time. The structure of the second class have much better query time but need more storage and preprocessing time. Both classes can be tuned to obtain different structures with different trade-offs for query time, memory cost and preprocessing time. In addition, the authors introduce a new weight-balanced multiway tree and use it to transform the previous static structures into dynamic structures with reasonable insertion and deletion times. Finally, they apply the results to the d-dimensional range searching problem and obtain a whole class of structures containing most of the known results and adding new ones.
- A technique for adding range restrictions to generalized searching problems
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Simplex Range Searching and Its Variants: A Review
- On algorithms for decomposable constraints
- Generalizations in the linear search problem
- Features of solving the range searching problems for d-dimensional case
- Lower Bounds on the Complexity of Polytope Range Searching
- An Additive Bounding Procedure for Combinatorial Optimization Problems
- On range searching with semialgebraic sets
- On range searching with semialgebraic sets
- Efficient splitting and merging algorithms for order decomposable problems.
- Connected component and simple polygon intersection searching
- A technique for adding range restrictions to generalized searching problems
- Using persistent data structures for adding range restrictions to searching problems
- Efficient splitting and merging algorithms for order decomposable problems
- Simplex Range Searching and Its Variants: A Review
- Connected component and simple polygon intersection searching
- Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines
This page was built for publication: General methods for adding range restrictions to decomposable searching problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1118417)