Search

A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q , our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q. [ABSTRACT FROM AUTHOR]

This work generalizes the classical problem of finding the largest empty rectangle among obstacles in 2D. Given a set P of n points, here a maximal empty rectangle (MER) is defined as a rectangle of arbitrary orientation such that each of its four boundaries contain at least one member of P and the interior of the rectangle is empty. We propose a very simple algorithm based on standard data structure to locate a MER of largest area in the plane. The worst-case time complexity of our algorithm is O(n3). Though the worst-case space complexity is O(n2), it reserves O(nlogn) space on an average to maintain the required data structure during the execution of the algorithm. [Copyright &y& Elsevier]

Let P be a set of n points, where each point is colored with one of the k possible colors. We present efficient algorithms to preprocess P such that for a given query point q , we can quickly identify the smallest color spanning object of the desired type containing q. In this paper, we focus on (i) intervals, (ii) axis-parallel square, (i i i) axis-parallel rectangle, (i v) equilateral triangle of fixed orientation and (v) circle, as our desired type of objects. [ABSTRACT FROM AUTHOR]

Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P = P r ∪ P b in R 2 and R 3 , where P r and P b represent a set of n red points and a set of m blue points respectively, and the objective is to compute a monochromatic object of a desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R 2 , and (ii) an axis-parallel monochromatic cuboid of maximum size in R 3. The time complexities of the algorithms for problems (i) and (ii) are O (m (m + n) (m n + m log m + n log n)) and O (m 3 n + m 2 n log n) , respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree , that was originally invented by J. L. Bentley in 1975. Our in-place variant of the k -d tree for a set of n points in R k supports orthogonal range counting query using O (1) extra workspace, and with O (n 1 − 1 ∕ k) query time complexity. The construction time of this data structure is O (n log n). Both the construction and query algorithms are non-recursive in nature that do not need O (log n) size recursion stack compared to the previously known construction algorithm for in-place k -d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P = P r ∪ P b , where each point in P b (resp. P r) is associated with a negative (resp. positive) real-valued weight that runs in O (m 2 (n + m) log (n + m)) time using O (n) extra space. [ABSTRACT FROM AUTHOR]

We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the read-only and in-place setup. The input to the problem is a set R of n axis-parallel rectangular obstacles in R 2 . The objective is to answer the following query efficiently. Path-Query ( p , q ) : Given a pair of points p and q , report an axis-parallel path from p to q avoiding the obstacles in R . In the read-only setup, we show that Path-Query ( p , q ) problem can be solved in O ( n 2 s + n log s ) time using O ( s ) extra space. We also show that the existence of an x -monotone path and reporting it, if it exists, can be done with the same asymptotic time complexity. If the objective is to test the existence of an x y -monotone path between the given pair of points p and q avoiding the obstacles, and report it if exists, then our proposed algorithm needs O ( n 2 s + n log s + M s log n ) time with O ( s ) extra space, where M s is the time complexity for computing the median of n elements in the read-only setup using O ( s ) extra space. Finally, we show that when the obstacles are unit squares instead of rectangles of arbitrary size, then there always exists a path of O ( n ) links between a pair of query points, and the path can be reported in O ( n n ) time using O ( 1 ) extra work-space. It is also shown that there is an instance where the minimum number of links in a path between a pair of specified points is O ( n ) . The objective of the Path-Query ( p , q ) in the in-place setup is to preprocess the input rectangles in a data structure in the input array itself such that for any pair of query points p and q , a rectilinear path can be reported efficiently. Here we propose an algorithm with O ( n log n ) preprocessing time and O ( n 3 / 4 + χ ) query time, where χ is the number of links (bends) in the path. Both the preprocessing and query answering need O ( 1 ) extra space. [ABSTRACT FROM AUTHOR]