Efficient searching with linear constraints

DOI10.1006/JCSS.2000.1709MaRDI QIDQ1591152zbMATH OpenOpenAlexFDO

Authors Lars Arge, Jeff Erickson, Paulo G. Franciosa, Jeffrey Scott Vitter, Pankaj K. Agarwal

Publication date 2 April 2001

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2000.1709

zbMATH Keywords

halfspace range searching

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Linear search with bounded resources
• scientific article; zbMATH DE number 519598
• An efficient search direction for linear programming problems
• A general framework for searching on a line
• A general framework for searching on a line
• Performance of linear-space search algorithms
• An efficient representation for linear constraints
• A rapidly convergence algorithm for linear search and application

Cites work

• scientific article; zbMATH DE number 2185627 (Why is no real title available?)
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1256735 (Why is no real title available?)
• scientific article; zbMATH DE number 1554935 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 910894 (Why is no real title available?)
• scientific article; zbMATH DE number 1424305 (Why is no real title available?)
• Applications of random sampling in computational geometry. II
• Constructing Belts in Two-Dimensional Arrangements with Applications
• Efficient partition trees
• Efficient searching with linear constraints
• Filtering Search: A New Approach to Query-Answering
• Halfspace range search: An algorithmic application of k-sets
• Improved bounds for planar k-sets and related problems
• Indexing for data models with constraints and classes
• Intersection Queries in Curved Objects
• Maintenance of configurations in the plane
• New upper bounds for neighbor searching
• On levels in arrangements of lines, segments, planes, and triangles
• Organization and maintenance of large ordered indexes
• Polygon Retrieval
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Reporting points in halfspaces
• The power of geometric duality
• -nets and simplex range queries

Cited in

(16)

• A general framework for searching on a line
• Performance of linear-space search algorithms
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Efficient searching with linear constraints
• Robust shape fitting via peeling and grating coresets
• Indexing moving points
• A general approach for cache-oblivious range reporting and approximate range counting
• Approximate Range Searching in External Memory
• Linearizing partial search orders
• Cache-oblivious range reporting with optimal queries requires superlinear space
• Approximate range searching in external memory
• Linear-space best-first search
• scientific article; zbMATH DE number 1554935 (Why is no real title available?)
• On Dominance Reporting in 3D
• Optimal partition trees
• Sequential search with a budget constraint

This page was built for publication: Efficient searching with linear constraints

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