research-article

Fractional cascading: II. Applications

Authors:

Bernard Chazelle,

Leonidas J. GuibasAuthors Info & Claims

Algorithmica, Volume 1, Issue 1-4

Pages 163 - 191

https://doi.org/10.1007/BF01840441

Published: 22 March 2023 Publication History

Abstract

This paper presents several applications offractional cascading, a new searching technique which has been described in a companion paper. The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.

References

[1]

Bentley J. L. Multidimensional divide and conquer Commun. ACM 1880 23 4 214-229

[2]

Bentley J. L. and Saxe J. B. Decomposable searching problems I: static to dynamic transformations J. Algorithms 1980 1 301-358

[3]

J. L. Bentley and M. I. Shamos.A problem in multivariate statistics: Algorithms, datastructures and applications. Proc. 15th Allerton Conf. Comm., Contr., and Comput. (1977), 193–201.

[4]

Bentley J. L. and Wood D. An Optimal worst-case algorithm for reporting intersections of rectangles IEEE Trans. Comput. 1980 C-29 571-577

[5]

B. Chazelle.Filtering search: A new approach to query-answering. Proc. 24th Ann. Symp. Found. Comput. Sci. (1983), 122–132. To appear in SIAM J. Comput. (1986).

[6]

B. Chazelle.How to search in history. Inform, and Control (1985).

[7]

B. Chazelle.A functional approach to data structures and its use in multidimensional searching. Brown Univ. Tech. Rept, CS-85-16, Sept. 1985 (preliminary version in 26th FOCS, 1985).

[8]

Chazelle B., Cole R., Preparata F. P., and Yap C. K. New upper bounds for neighbor searching 1984 Providence, RI Brown University

[9]

B. Chazelle and H. Edelsbrunner.Linear space data structures for a class of range search. To appear in Proc. 2nd ACM Symposium on Computational Geometry, 1986.

[10]

B. Chazelle and L. J. Guibas.Visibility and intersection problems in plane geometry. Proc. 1st ACM Symposium on Computational Geometry, Baltimore, MD, June 1985, pp. 135–146.

[11]

Chazelle B., Guibas L. J., and Lee D. T. The power of geometric duality BIT 1985 25 1

[12]

Cole R. Searching and storing similar lists 1983 New York Courant Inst., New York University

[13]

R. Cole and C. K. Yap.Geometric retrieval problems, Proc. 24th Ann. Symp. Found. Comput. Sci. (1983), 112–121.

[14]

D. P. Dobkin and H. Edelsbrunner.Space searching for intersection objects. Proc. 25th Ann. Symp. Found. Comput. Sci. (1984).

[15]

D. P. Dobkin and J. I. Munro.Efficient uses of the past. Proc. 21st Ann. Symp. Found. Comput. Sci. (1980), 200–206.

[16]

Edelsbrunner H. Intersection problems in computational geometry Ph.D. Thesis 1982 Austria IIG, Univ. Graz

[17]

H. Edelsbrunner, L. J. Guibas, and J. Stolfi.Optimal point location in a monotone subdivision. To appear.

[18]

Edelsbrunner H. and Huber F. Dissecting sets of points in two and three dimensions Forthcoming technical report 1984 Austria IIG, University of Graz

[19]

Edelsbrunner H., Kirkpatrick D. G., and Maurer H. A. Polygonal intersection search In-form. Process. Lett 1982 14 74-79

[20]

Edelsbrunner H. and Welzl E. Halfplanar range search in linear space and O(n^0.695)query time 1983 Austria University of Graz

[21]

H. N. Gabow, J. L. Bentley, and R. E. Tarjan.Scaling and related techniques for geometry problems. Proc. 16th Ann. SIGACT Symp. (1984), 135–143.

[22]

Knuth D. E. The art of computer programming, sorting and searching, Vol. 3 1973 Reading, MA Addison-Wesley

[23]

Lee D. T. and Preparata F. P. Location of a point in a planar subdivision and its applications SIAM J. Comput 1977 6 3 594-606

[24]

E. M. McCreight.Efficient algorithms for enumerating intersecting intervals and rectangles. Tech. Rep., Xerox PARC, CSL-80-9 (June 1980).

[25]

E. M. McCreight.Priority search trees. Tech. Rep., Xerox PARC, CSL-81-5 (1981).

[26]

Overmars M. H. The design of dynamic data structures PhD Thesis 1983 The Netherlands University of Utrecht

[27]

Tarjan R. E. A class of algorithms which require nonlinear time to maintain disjoint sets J. Comput. System Sci. 1979 18 110-127

[28]

D. E. Willard.New data structures for orthogonal queries. To appear in SIAM J. Comput.

[29]

F. F. Yao.A 3-space partition and its applications. Proc. 15th Annual SIGACT Symp. (1983), 258–263.

Cited By

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Wang QYi K(2023)Conjunctive Queries with ComparisonsACM SIGMOD Record10.1145/3604437.360445052:1(54-62)Online publication date: 8-Jun-2023
https://dl.acm.org/doi/10.1145/3604437.3604450
Vogelsgesang ANeumann TLeis VKemper AIves ZBonifati AEl Abbadi A(2022)Efficient Evaluation of Arbitrarily-Framed Holistic SQL Aggregates and Window FunctionsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526184(1243-1256)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526184
Show More Cited By

Recommendations

Fractional cascading: I. A data structuring technique
Abstract
In computational geometry many search problems and range queries can be solved by performing an iterative search for the same key in separate ordered lists. In this paper we show that, if these ordered lists can be put in a one-to-one ...
Content-Based Image Retrieval Using Iterative Search

The aim of Content-based Image Retrieval (CBIR) is to find a set of images that best match the query based on visual features. Most existing CBIR systems find similar images in low level features, while Text-based Image Retrieval (TBIR) systems find ...
Optimal cooperative search in fractional cascaded data structures

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 1, Issue 1-4

Nov 1986

517 pages

ISSN:0178-4617

Issue’s Table of Contents

© Springer-Verlag New York Inc. 1986.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 22 March 2023

Revision received: 18 February 1986

Received: 30 August 1985

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Wang QYi K(2023)Conjunctive Queries with ComparisonsACM SIGMOD Record10.1145/3604437.360445052:1(54-62)Online publication date: 8-Jun-2023
https://dl.acm.org/doi/10.1145/3604437.3604450
Vogelsgesang ANeumann TLeis VKemper AIves ZBonifati AEl Abbadi A(2022)Efficient Evaluation of Arbitrarily-Framed Holistic SQL Aggregates and Window FunctionsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526184(1243-1256)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526184
Wang QYi KIves ZBonifati AEl Abbadi A(2022)Conjunctive Queries with ComparisonsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517830(108-121)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517830
Chan THershberger JPratt S(2019)Two Approaches to Building Time-Windowed Geometric Data StructuresAlgorithmica10.1007/s00453-019-00588-381:9(3519-3533)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s00453-019-00588-3
Afshani PArge LLarsen KDey TWhitesides S(2012)Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine modelProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261299(323-332)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261299
Chan TLarsen KPătraşcu MHurtado Fvan Kreveld M(2011)Orthogonal range searching on the RAM, revisitedProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998198(1-10)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998198
Goodrich MSimons J(2011)Fully retroactive approximate range and nearest neighbor searchingProceedings of the 22nd international conference on Algorithms and Computation10.1007/978-3-642-25591-5_31(292-301)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25591-5_31
Afshani PArge LLarsen KKirkpatrick DMitchell J(2010)Orthogonal range reportingProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811001(240-246)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1810959.1811001
Gao JGuibas LHershberger JZhang LRamchandran KSztipanovits JHou JPappas T(2004)Fractionally cascaded information in a sensor networkProceedings of the 3rd international symposium on Information processing in sensor networks10.1145/984622.984668(311-319)Online publication date: 26-Apr-2004
https://dl.acm.org/doi/10.1145/984622.984668
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents