Computational Geometry,Generalized Intersection Searching:Summary of Known Results
Summary of Known Results
Generalized intersection searching problems were introduced by Janardan and Lopez in [23]. Subsequent work in this area may be found in [2, 3, 6–8, 16, 18–22, 29]. (Some of these results are also reported in two Ph.D. theses [17, 30].) In this section, we give a broad overview of the work on these problems to date; details may be found in the cited references.
In [23], efficient solutions were given for several generalized reporting problems, where the input objects and the query were axes-parallel. Examples of such input/query pairs considered include: points/interval in R1; line segments/segment, points/rectangle, and rectangles/rectangle, all in R2; and rectangles/points in Rd, where d ≥ 2 is a constant.
Several of these results were further extended in [18] to include counting and/or dynamic reporting, and new results were presented for input/query pairs such as intervals/interval in R1, points/quadrant in R2, and points/rectangle in R3. Furthermore, a new type of counting problem, called a type-2 counting problem was also introduced, where the goal was to count for each color intersected the number of objects of that color that are intersected. In [6], improved solutions were given for counting and/or reporting problems involving points/interval in R1, points/rectangle in R2, and line segments/segment in R2.
Arbitrarily-Oriented Objects
Efficient solutions were given in [23] for generalized reporting on non-intersecting line segments using a query line segment. Special, but interesting, cases of intersecting line segments, such as when each color class forms a polygon or a connected component, were considered in [3]. Efficient solutions were given in [19] for input/query pairs consisting of points/halfspace in Rd, points/fat-triangle, and fat-triangles/point in R2. (A fat-triangle is a triangle where each internal angle is at least a user-specified constant, hence “well- shaped”.) Some of these results were improved subsequently in [6]. In [20], alternative bounds were obtained for the fat-triangle problems within the framework of a general tech- nique for adding range restriction capability to a generalized data structure. Results were presented in [8] for querying, with a polygon, a set of polygons whose sides are oriented in at most a constant number of different directions, with a polygon. In [30], a general method was given for querying intersecting line segments with a segment and for querying points in Rd with a halfspace or a simplex. Generalized problems involving various combinations of circular objects (circles, discs, annuli) and points, lines, and line segments were considered in [21].
Problems on the Grid
Problems involving document retrieval or string manipulation can often be cast in the framework of generalized intersection searching. For example, in the context of document retrieval, the following problem (among others) was considered in [29]: Preprocess an array of colored non-negative integers (i.e., points on the 1-dimensional grid) such that, given two indices into the array, each distinct color for which there is a pair of points in the index range at distance less than a specified constant can be reported efficiently. In the context of substring indexing, the following problem was considered in [16]: Preprocess a set of colored points on the 1-dimensional grid, so that given two non-overlapping intervals, the list of distinct colors that occur in their intersection can be reported efficiently. I/O efficient algorithms were given in the standard external memory model [31] for this problem. Other grid-related work in this area includes [2], where efficient solutions were given for the points/rectangle and rectangles/point problems, under the condition that the input and query objects lie on a d-dimensional grid.
In this class of problems, we are given a collection of geometric objects and the goal is to report all pairs that intersect. Note that there is no query object as such here and no notion of preprocessing the input. As an example, suppose that we are given a set of convex polygons with a total of n vertices in R2, and we wish to report or count all pairs that intersect, with the goal of doing this in time proportional to the number of intersecting pairs (i.e., output-sensitively). If the number of polygons and their sizes are both functions of n (instead of one or the other being a constant), then, as discussed in [22], standard methods (e.g., testing each pair of polygons or computing all boundary intersections and polygon containments in the input) are inefficient. In [22], an efficient and output-sensitive algorithm was given for this problem. Each polygon was assigned a color and then decomposed into simpler elements, i.e., trapezoids, of the same color. The problem then became one of reporting all distinct color pairs (c1, c2) such that a trapezoid of color c1 intersects one of color c2. An improved algorithm was given subsequently in [1] for both R2 and R3. Other related work on such colored single-shot problems may be found in [7].
Comments
Post a Comment