Efficient searching with linear constraints

DOI10.1006/JCSS.2000.1709zbMATH Open0966.68061OpenAlexW4210591609MaRDI QIDQ1591152FDOQ1591152

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

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

zbMATH Keywords

halfspace range searching

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

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

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
• Approximate Range Searching in External Memory
• A general approach for cache-oblivious range reporting and approximate range counting
• 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
• Title not available (Why is that?)
• 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)