The Complexity of Searching Lines in the Plane: Preliminary Version.
Abstract
Searching is a fundamental operation of computer science. Yet a number of key mathematical questions about searching in Euclidian spaces remains open. A number of such questions are formulated and answered here for searching lines in the plane. Relationships between the results here and higher dimensional analogs for other problems of interest are given. Among the new results is a mathematical framework in which questions about searching can be stated in a more uniform manner than was possible before. Specific results are also given on the searching complexity of various sets of lines in the plane. In particular, it is shown that there are easy and hard sets of lines to search and establish methods of generating upper and lower bounds on the search complexities of such sets.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1975
- Accession Number
- ADA039872
Entities
People
- David Dobkin
- Richard J. Lipton
Organizations
- Yale University