Fractional Cascading - Applications


Typical applications of fractional cascading involve range search data structures in computational geometry. For example, consider the problem of half-plane range reporting: that is, intersecting a fixed set of n points with a query half-plane and listing all the points in the intersection. The problem is to structure the points in such a way that a query of this type may be answered efficiently in terms of the intersection size h. One structure that can be used for this purpose is the convex layers of the input point set, a family of nested convex polygons consisting of the convex hull of the point set and the recursively-constructed convex layers of the remaining points. Within a single layer, the points inside the query half-plane may be found by performing a binary search for the half-plane boundary line's slope among the sorted sequence of convex polygon edge slopes, leading to the polygon vertex that is inside the query half-plane and farthest from its boundary, and then sequentially searching along the polygon edges to find all other vertices inside the query half-plane. The whole half-plane range reporting problem may be solved by repeating this search procedure starting from the outermost layer and continuing inwards until reaching a layer that is disjoint from the query halfspace. Fractional cascading speeds up the successive binary searches among the sequences of polygon edge slopes in each layer, leading to a data structure for this problem with space O(n) and query time O(log n + h). The data structure may be constructed in time O(n log n) by an algorithm of Chazelle (1985). As in our example, this application involves binary searches in a linear sequence of lists (the nested sequence of the convex layers), so the catalog graph is just a path.

Another application of fractional cascading in geometric data structures concerns point location in a monotone subdivision, that is, a partition of the plane into polygons such that any vertical line intersects any polygon in at most two points. As Edelsbrunner, Guibas & Stolfi (1986) showed, this problem can be solved by finding a sequence of polygonal paths that stretch from left to right across the subdivision, and binary searching for the lowest of these paths that is above the query point. Testing whether the query point is above or below one of the paths can itself be solved as a binary search problem, searching for the x coordinate of the points among the x coordinates of the path vertices to determine which path edge might be above or below the query point. Thus, each point location query can be solved as an outer layer of binary search among the paths, each step of which itself performs a binary search among x coordinates of vertices. Fractional cascading can be used to speed up the time for the inner binary searches, reducing the total time per query to O(log n) using a data structure with space O(n). In this application the catalog graph is a tree representing the possible search sequences of the outer binary search.

Beyond computational geometry, Lakshman & Stiliadis (1998) and Buddhikot, Suri & Waldvogel (1999) apply fractional cascading in the design of data structures for fast packet filtering in internet routers. Gao et al. (2004) use fractional cascading as a model for data distribution and retrieval in sensor networks.

Read more about this topic:  Fractional Cascading

Other articles related to "applications, application":

Transistor - Comparison With Vacuum Tubes - Advantages
... that have allowed transistors to replace their vacuum tube predecessors in most applications are Small size and minimal weight, allowing the development of miniaturized electronic devices ... voltages, making transistors suitable for small, battery-powered applications ... for cathode heaters required after power application ...
Biotechnology - Applications - Agriculture - Improved Taste, Texture or Appearance of Food
... The first genetically modified food product was a tomato which was transformed to delay its ripening ... Researchers in Indonesia, Malaysia, Thailand, Philippines and Vietnam are currently working on delayed-ripening papaya in collaboration with the University of Nottingham and Zeneca ...
X Servers - Limitations and Criticism - Network
... similar to GNU Screen in relation to terminals), and other applications and toolkits provide related facilities ... interface (mouse, keyboard, monitor) of a running application to be switched from one location to another without stopping and restarting the application ... This can be important in some applications, such as process monitoring and control ...
Photoresist Categories - Applications
... Microelectronics This application, mainly applied to silicon wafers/silicon integrated circuits is the most developed of the technologies and the most ...
Building On OpenStep
... idea was to use OpenStep code as a basis for network-wide applications running across different platforms, as opposed to using CORBA or some other system ... Unlike OpenStep, which defined an operating system that applications would run in, under PDO the libraries were compiled into the application itself, creating a stand-alone "native" application for a particular platform ... amount of supporting code (Objective-C and the libraries), PDO applications were nevertheless considerably smaller than similar CORBA solutions, typically about one-half to one-third the size ...