ABSTRACT

Let be a set of points in two dimensional plane. For each point, we locate an axisparallel unit square having one particular side passing through and enclosing the maximum number of points from. Considering all points, such squares can be reported in time. We show that this result can be used to (i) locate axis-parallel unit squares which are pairwise disjoint and they together enclose the maximum number of points from (if exists) and (ii) find the smallest axis-parallel square enclosing at least points of,.

Keywords:Axis-Parallel Unit Square, Sweep Line Algorithm, Maximium Enclosing Problem, K-Enclosing Problem

1. Introduction

Given a set points in a plane, enclosing problem in computational geometry is concerned with finding the smallest geometrical object of a given type that encloses all the points of. Some well known instances of the enclosing problem are finding minimum enclosing circle [1] , minimum area triangle [2] , minimum area rectangle [3] , minimum bounding box [4] , and smallest width annulus [5] .

The -enclosing problem is an important variant of enclosing problem. Here the objective is to compute a smallest region of given type that encloses at least points of. -enclosing problems using rectangles and squares are studied [6] -[11] are also studied extensively.

A closely related problem locates one or more copies of a given region to maximize the size of the subset enclosed. In other words, instead of fixing and computing an optimal enclosing region, the problem is to maximize the number of points enclosed by the given region(s) of fixed size and shape. This type of problem has similar applications as the problems mentioned above. These so called problems of maximal enclosing using single object, each of fixed size and orientation, have also received attention of many researchers. The objects used are circle [12] and convex polygon [13] [14] . Younies et al. [15] introduced a zero-one mixed integer formulation for the maximum enclosing problem where points are enclosed by parallelograms in a plane. Directional antennas is one of the applications where parallelogram shapes would be useful. In the context of bichromatic planar point set, Díaz-Báñez et al. [16] proposed algorithms for maximal enclosing by two disjoint axis-parallel unit squares and circles in and time respectively. Later, they improved the complexities to and time respectively [17] .

Problems Studied

An axis-parallel unit square is a square of unit size whose sides are parallel to one of the coordinate axes. An axis-parallel unit square encloses a set of points those lie on the boundaries of or in the interior of. For a given set of points in two dimensional plane, in this paper we consider the following variation of the maximal covering problem.

• For each point, locate an axis-parallel unit square whose one side is constrained to pass through and encloses the maximum number of points from.

We propose an time and space algorithm to solve the problem P1. It is shown that this algorithm can be used to compute a placement of one or more axis-parallel squares enclosing the maximum number of points from if such a placement exists. We also use this result to construct an efficient algorithm for finding the smallest axis-parallel square enclosing at least points of for large values of .

2 Maximal Enclosing Problem

This section considers the following problem P1: For each point, we locate an axis-parallel unit square whose one particular side is passing through and enclosing the maximum number of points from. Note that such axis-parallel unit square may not be unique. In that case, choose one among them and call that axis-parallel unit square as candidate square. Therefore, at most number of candidate squares can be obtained by considering alignments of four different sides for all points in. Below we describe the pass for computing candidate squares whose bottom sides are passing through a point from (See Figure 1).

Without loss of generality, assume that no two points have the same - or -coordinate. Consider two arrays and containing the points of in ascending order of and -coordinates respectively. Let us denote the -coordinate of the i-th entry of by and similarly the -coordinate of the i-th entry of by,. Coordinates of a generic point is denoted by. For a point, let denote the minimum entry in, say, such that.

Observation 1 Given the array, all intervals, can be computed in linear time.

In a similar way, for a point, let denote the minimum entry in, say, such that. Likewise, we define, and on the arrays and respectively.

Algorithm for Reporting Candidate Squares

In this section we present sweep line algorithm combined with balanced search tree as data structure for computing candidate squares. Using the points in array, construct a balanced search tree with search key as the -coordinate values of the points in. The leaves of correspond to the ordered points of. We attach two positive integral variables and with each node of. Before describing the algorithm in details, we first explain the role of and. The span corresponding to an internal node is an interval, generated by the -coordinates of the left most and right most points at the leaves in the subtree rooted at. Moreover, span of the leaf node stores the -coordinate of the point at the leaf node of. Our sweep line algorithm considers two horizontal sweep lines namely bottom sweep line and top sweep line. Let the current positions of and be at heights and respectively such that and be the unit horizontal slab determined by and. In case that the vertical distance between and is less than unity, shift upwards to create a gap between and as unity. Note that, no additional points are included for such shifting of in upward direction.

At the end of processing all points within, we get the following information by and. The variable attached with an internal node indicates that there exists a subset of size (i.e., stores the count of the set) such that each unit square whose bottom, top sides coincide with, respectively and left boundary within span encloses the subset. Observe that these spans are all different for all nodes. The subsets for nodes along the path from root to a leaf node are all disjoint. Here each node does not keep explicitly but only its count. The variable attached with an internal node indicates that there exists a unit square whose cardinality is the sum of values of the ancestor nodes of plus the value at node; bottom and top sides of are constrained to coincide with, respectively, the left boundary of lies within the span. Moreover, the cardinality of is maximum among all unit squares within the slab and the left boundary of each such unit square lies within the span of. We now recursively define value for an internal node as the sum of its value and the maximum of values of its two children-nodes. This recursive definition of implies that variable at the root of tree stores the cardinality of a candidate square whose bottom side is constrained to pass through the point. This type of integral variables attached to the nodes of segment tree are also used to handle stabbing counting queries [18] . The space requirement for this type of segment tree is linear [18] .

In initial step, the variables and corresponding to all nodes are initialized with zero and both the sweep lines and pass through the bottom most point. Assume that is the point corresponding to the i-th entry in,. The algorithm processes all points in one at a time. We also explain the way of capturing information by the variables and at the time of processing a point in, encountered by sweep lines.

The sweep line is moved up one point at a time, considering as the first encountered point. For each point encountered by the sweep line, if the vertical distance of from the current position of the sweep line is less than or equal to unity, is updated by Increment operation which is described below.

For the interval, find the split node [18] in, that is the least common ancestor of and in the balanced search tree. Search for the leaf node containing on the left subtree rooted at and, while traversing, if we turn left from node, increment of the right child of by one. In case the right child of is a leaf, increment its instead of. Similarly, while traversing the right subtree of the split node for searching the leaf node containing, if we turn right from node, increment of the left child of. Again, in case the left child is a leaf, increment its instead of. Finally, increase the values of the leaf nodes containing and by one. We now recursively update the value of each internal node in the path from the leaf node containing to the left child of the split node, as the sum of its value and the maximum of values of its two children-nodes. Then update the value of each internal node in the path from the leaf containing to the root of in similar way. In case, we find the leaf node of that contains the point and increment the value of leaf node. The subsequent updation of values associated with the internal nodes of is same as described earlier.

Again if the vertical distance of the encountered point by from the current position of becomes greater than unity, stops advancing to (i.e., is not updated by Increment operation for the point). For the point on the current position of, update for the point and report a candidate square with bottom boundary passing though by the Decrement and Report operations which are explained below. The sweep line is then moved up one point at a time. For each point encountered by the sweep line, if the vertical distance between and is greater than unity, is updated by Decrement operation and a candidate square with bottom boundary passing though is reported by Report operation.

In case that the vertical distance of from becomes smaller than unity, the sweep line stops advancing and sweep line starts sweeping from its current position. The above process is continued till Report and Decrement operations are done for all the points.

We now describe the Report operation. Let be the candidate square with bottom boundary passing through the point. Observe that the number of points enclosed by is equal to the value at the root of the tree. To find a placement of the left boundary of, move from the root of the tree towards the leaf, each time picking the child with larger value. The leaf node thus reached stores the point through which the left boundary of passes. Report along with the number of points inside it.

The Decrement operation is same as Increment operation with the following exception. For the interval associated with point, locate the split node in. During searching from the split node for the nodes containing and, instead of incrementing, we decrement’s and’s by one as appropriate. The subsequent updation of values associated with the internal nodes of is similar to that in the Increment operation.

Theorem 1 Let be a set of points in a two dimensional plane. Then all candidate squares for, , can be computed in time using space.

Proof: For a point, each of Increment, Decrement and Report operation takes time. Since for each point in, these operations are executed only once, they together take time. Corollary 1 A placement of an axis-parallel unit square enclosing the maximum number of points from can be computed in time using space.

Proof: Let be an axis-parallel unit square enclosing the maximum number of points from and be the set of points enclosed by. Note that can always be repositioned, without altering the points enclosed by it, so that the extended lines of two adjacent sides of pass through two points of and these two points may not belong to. Sometimes the adjacent sides of may be passed through same point of and, in that case, the point is at one corner of. Therefore, the maximum cardinality among the set of all possible candidate squares is equal to the cardinality of. Corollary 2 An axis-parallel rectangle of fixed height and width that encloses the maximum number of points from, can be placed in time using space.

Proof: Follows directly from Corollary 1. Corollary 3 A placement of two disjoint axis-parallel unit squares together enclosing the maximum number of points from, can be computed in time using space.

Proof: For each point, we can compute the cardinality of candidate square whose top boundary is passing through in time. Now, we sweep from bottom to top to generate a subset of that reports the maximum cardinality candidate square whose top boundary lies below any point. This sweeping process requires time. It is interesting to generalize the maximal enclosing problem using disjoint axis-parallel unit squares, and the problem is known to be NP-hard [19] . A set of rectangles (squares) on the plane is called -sliceable if they can be recursively partitioned by horizontal or vertical lines [20] . We now assume there exists -sliceable axis-parallel squares and propose an algorithm to locate three axis-parallel unit squares which are pairwise disjoint and they together enclose the maximum number of points from.

Let and be the points with maximum -coordinates and minimum -coordinates among the points in respectively. Similarly, and be the points with maximum -coordinates and minimum -coordinates among the points in respectively.

Observe that among these three squares, one square is separated from other two squares by a horizontal or a vertical line. Without loss of generality, assume that the line separating one square from other two squares is vertical (first pass). The other pass where the line separation is horizontal, can be handled in similar manner. Now we are describing the first pass of our proposed algorithm.

Let the vertical line passing through the i-th point in array divides the point set into two sub-set and respectively; the subset and lie on the left and right side of this vertical line. For the position of the vertical line that passes through the i-point of, the result in Corollary 3 is used to place a pair of disjoint squares enclosing the maximum number of points from and the result in Corollary 1 to place a square that encloses the maximum number of points from. This triplate of squares is a potential candidate for position of the vertical line that passes through the -th entry of. Observe that the time required to place these triplet of squares is. Similarly use the result in Corollary 1 to place a square that encloses the maximum number of points from and the result in Corollary 3 to place a pair of disjoint squares enclosing the maximum number of points from. This triplate of squares is also a potential candidate for position of the vertical line that passes through the i-th entry of. Finally, a triplate of squares that together enclose greater number of points of among the two sets of triplet of squares is kept. Now this process is repeated for each position of the vertical line that passes though a point. We thus have the following result.

Corollary 4 Given a set of points in the plane, three axis-parallel unit squares which are pairwise disjoint and they together enclose the maximum number of points from can be placed in time and space.

To solve the maximal enclosing problem using axis-parallel unit squares, if we naively extend this approach then it is interesting to note that the solution would not have a polynomial time complexity in both and. Now to solve this problem, we propose an time and space algorithm that uses (i) similar dynamic programming approach as proposed by Mukherjee et al. [21] , and (ii) the result in Corollary 1 as a subroutine.

Observe that placing horizontal and vertical partitioning lines among the points of can generate subsets of. Let be the subset of points enclosed by the minimum enclosing rectangle (MER) defined by the points and, and as bottom-left and top-right corners respectively. Given a subset, let denote the maximum number of points from jointly enclosed by disjoint axis-parallel unit squares placed over the subset.

In the first step, we compute for all possible subsets of using the result in Corollary 1. Subsequently, it computes for all possible subsets of using the results of the previous steps in similar dynamic programming approach as proposed by Mukherjee et al. [21] . Finally, it reports.

In view of the Corollary 1, computation of the first step requires. Complexity of subsequent steps, and hence, the over all time complexity of the algorithm is. Corresponding space complexity can also be shown to be. Further details can be found in [21] . We thus have the following result.

Theorem 2 A placement of sliceable axis-parallel unit squares which are pairwise disjoint and they together enclose the maximum number of points from can be computed in time using space.

3. k-Enclosing Problem

Initially researchers considered the -enclosing problem for computing a smallest area (perimeter) axis-parallel square or rectangle. Most of the algorithms proposed for -enclosing problems are efficient when is small and become inefficient for large values of. Segal and Kedem [9] presented an time algorithm for finding a smallest area -enclosing axis-parallel rectangle for large values of,.

Matoušek [22] developed, , time algorithm to find a smallest -enclosing circle that is especially efficient when is close to. Given a set of points in the plane and an integer , we consider the problem of computing the minimum area axis-parallel square that encloses at least points of for large values of. A point enclosing square (rectangle) is said to be a -square (- rectangle) if there does not exist another square (rectangle) having area less than that of and enclosing points from [10] .

We use the idea of prune and search technique to solve the optimization problem for finding .

Each pruning step uses the solution of the corresponding decision problem that guides the search process. The decision version of this problem asks whether there exists a square of side length that encloses at least points where and are the input parameters. In Section 4, we present some preliminary observations and it is shown that the Result in Corollary 1 can be used to solve a decision version of the optimization problem.

4. Preliminaries

Let be the set of points in the plane. Our objective is to compute -square. Without loss of generality, assume that no two points of have the same or coordinates. Let and denote the -coordinate and the -coordinate of any point respectively. The size of a square is represented by the length of it's side. We have the following observation.

Observation 2 At least one pair of opposite sides of must contain points from.

The decision version of this problem can be stated as “given a length, does there exist a square of size that encloses at least points of?”.

Let, , , and be five subsets of such that and all the subsets are not necessarily mutually disjoint. We define and as the set of bottom most and top most points of respectively; and are the set of left most points and right most points of respectively; and where.

Note that if then must contain at least one point of. The following observation follows from the above definitions.

Observation 3 For, must enclose all the points of.

Proof: Let be any point of the set. At least elements are on the right side of. The position of in the left to right ordering of are at most. Therefore there are number of points of on the left of for. Consequently at most points are on left of. Hence right boundary of is on right side of. Similarly left, top and bottom boundaries of are on left, top and bottom sides of respectively. Hence the observation follows.

Let be the minimum area axis-parallel rectangle enclosing the point set. Suppose the length of the longest side of is and the left, right, top and bottom boundaries of the rectangle contain the points, , and respectively (See Figure 2). We define, as an axis-parallel square of size that includes the point set and the total number of points enclosed from is maximized. It is easy to see that the bottom, top, left and right boundaries of must lie within the ranges, , and respectively.

To locate among the set, we use sweep line paradigm combined with binary search tree as data structure in similar way as described in Section 2.1. As earlier, our algorithm makes horizontal and vertical sweeps. Below we briefly describe the algorithm for horizontal sweep to locate whose bottom side is aligned with a point from. Look for all squares of size whose bottom and left boundaries are within the range and respectively.

Now consider possible positions of the left boundary of within the above mentioned range such that the left boundary or the right boundary passes through a point of. Notice that all squares with these restrictions include the point set. Therefore the points in the set are the only points required to be processed to locate and the number of such points is at most. This observation leads to the following theorem.

Corollary 5 For given, the axis-parallel square containing the maximum number of points from and enclosing point set can be located in time using space.

5. An Efficient Algorithm to Find k-Square for Large Values of k

In this section, we explain an efficient algorithm to find for large values of. The result in Corollary 5 to locate is used as a subroutine to find for. From Observation 2, we can conclude that either top and bottom sides of contain points of or left and right sides of contain points of. Without loss of generality, assume that top and bottom sides of contain points from. The other case where left and right sides of contain points of, can be handled in similar manner. Let be an ordering of points of the set in increasing order of their -coordinate values. Consider to be the list of vertical distances, for each pair of points and.

Our objective is to find for a given value such that encloses points of and the value is minimized. We iteratively reduce the size of by prune and search technique without explicitly computing elements of. Let represent the list of vertical distances at iteration. At iteration we reduce the size of by. Initially. Observe that for any, for. Without loss of generality, let the indices of the points and remain same in also. Let us denote the set of vertical distances generating by the sequences defined as follows.

Note that the elements in each sequence are in nondecreasing order. At iterative step of the algorithm the current search space is reduced by pruning the’s. Here, either upper or lower portion of is pruned. Therefore, each sequence can be represented by lower and upper indices of the original sequence. For any point, median element of the corresponding sequence is

where and are the lower and upper indices of the sequence. We denote the median element of as. So computing the median of the sequence of vertical distances corresponding to any point requires only a constant time arithmetic operation on the array indices.

We represent each as a vertical strip parallel to the -axis. All the vertical strips (’s) are arranged along the -axis such that 's fall on the -axis and the median values are in nonincreasing order along the -axis (See Figure 3). Again the elements of each are arranged in nondecreasing order parallel to the -axis. At initial step of iteration, all medians are in nonincreasing order. This ordering may change in subsequent iterations due to pruning of 's. Therefore at each iteration, we need to rearrange’s such that’s are in nonincreasing order. Let be an arrangement of the sequences in such that. At iteration we

find an index such that is half of the size of. Observe that the size of is at most of the size of. Consider as and compute Max-. If encloses at least points of, then size of is less than or equal to and we can ignore the elements in greater than. Note that all the values corresponding to are greater than. Therefore for each we can delete upper half of. In case, encloses less than points, we similarly delete lower half of each for. Now continue with the subsequent iterations until we end up at an iteration, say maxit, such that size of is constant.

Lemma 1 At every iterative step the size of the current solution space is reduced by a factor of.

Proof: At iteration, either we discard upper half of or lower half of. As the total number of elements in the sequences is of size of, we can discard at least elements of. Similar amount of elements is discarded for pruning of lower half. Now we have the following theorem.

Theorem 3 Given a set of points in the plane and an integer, the smallest area square enclosing at least points of can be computed in time using linear space.

Proof: Partitioning the set to generate subsets and requires time. Sorting the points of the sets and with respect to their -coordinates requires time. We do not store the 's explicitly. Instead, for all 's, we maintain an array whose each element contains the index information and for at each iteration. So for each we need only an additional constant amount of space. Altogether in linear amount of space we can execute our algorithm. Time complexity can be established from the following algorithmic steps at iteration.

• Computation of for each requires constant amount of time.

• Sorting the set of all medians takes time.

• Determining such that is half of the size of, needs time.

• Computation of takes time (see Theorem 5).

• We maintain the index structure of the arrays. This involves updating of and for each when half of it's elements are discarded. This step requires constant amount of time for each.

From Lemma 1, we get that at iterative step at least elements are discarded where denotes the size of. This leads to the following recurrence relation.

(1)

Hence the theorem. The technique used to derive the result in Theorem 3 can also compute for all values of. Hence we have the following theorem.

Theorem 4 Given a set of points in the plane and an integer, the smallest area square enclosing at least points of can be computed in time using linear amount of space.

Acknowledgments

This research was partially supported by the DST PURSE scheme at University of Kalayni, India.

References