Report On Seminar(parametric Searching) By Indranil Nandy(06cs6010)

Indian Institute of Technology Kharagpur – 721302

Seminar Report Topic : Parametric Search – what it is and how to make it practical

Submitted by : Name : Indranil Nandy Course : MTech,2006 Roll no : 06CS6010 e-mail : [email protected]

Under the guidance of : Prof. Arijit Bishnu

INTRODUCTION: Since the late 1980s, parametric search, the optimization technique developed by Megiddo in the late 1970s and early 1980s, has become an important tool for solving many geometric optimization queries efficiently. The main principle of parametric search is to compute a value λ* that optimizes an objective function f with the use of an algorithm As that solves the corresponding decision problem. The decision problem can be stated as follows: given a value λ, decide whether λ < λ*, λ = λ*, or λ > λ*. The idea is to run a “generic” version AGs on the unknown value λ*. This generic algorithm uses the concrete versionf As to determine the outcome of the decision problem for a set of concrete values; for one of these values λ, As will report that λ = λ*. The technique will be explained in more detail in next section. Usually, applying the concrete version As is expensive in terms of running time. Megiddo shows how using a parallel version Ap of As as the generic algorithm may reduce the number of times As is called considerably. The technique is rather complicated, as it requires the design of an efficient parallel algorithm. Fortunately, the generic algorithm does not necessarily have to solve the same problem as the concrete decision; in several cases, sorting can be used instead. However, the existing parallel sorting algorithms that have good worst-case time bounds are not easily implemented, and in some cases the hidden constants in the asymptotic running times are enormous.

How It Works? Megiddo’s parametric-search technique works as follows: assume that we have a decision problem P(λ) that is monotonous in λ, i.e., if P(λ0) is true, then P(λ) is true for all λ < λ0. Our task is to find λ*, the maximum value of λ for which P(λ) is true. Suppose that we have an algorithm As that solves the decision problem P, and that can determine for any input value λ whether λ < λ*, λ = λ*, or λ > λ*. Also suppose that the flow of control of As depends on comparisons, each of which depends on the sign of a polynomial in λ.  For Parametric Searching to be used it must have the following property :  we have an algorithm As that solves the decision problem P, and that can determine for any input value λ whether λ < λ*, λ = λ*, or λ > λ* [It may seem strange that we do not know λ*,then how to compare any given input with λ *…mainly the equality test? Think for the previously given example, there if we know the equation of AB then it is possible to say for any λ whether q(λ) is on AB (i.e. λ = λ*) or it lies on the left (i.e. λ < λ*) or on the right(λ >λ*),though we do not know λ*!!]  the flow of control of As depends on comparisons Here is two slide presentations :

fig. 1

fig. 2

Megiddo’s idea is to run As generically on the unknown input λ* [see the slide presentation fig.6 below]. However, we get to know the actual value of λ* as a byproduct of running AGs on λ*. During the generic execution of AGs we maintain an open interval I in which λ* is known to lie; initially, I is (-∞;∞) [This interval may also be finite, see the presentation slide fig.3 below].

fig. 3 Whenever a comparison has to be resolved, we need to determine the sign of polynomial p at the value λ*[any comparison between two rational bounded function of t can be reduced to the checking of the sign of a polynomial at the value t, for further details see fig 4 & fig5 below]. This can be done without knowing the value of λ*, by running the concrete version As on the roots of p[we can use Newton’s Approximation technique for this; as p is a rational bounded function, total number of roots is also bounded; so it can be found in O(1) time; see fig.7 below].

fig 4

fig.5 This determines the location of λ* among the roots, i.e., it either gives us two consecutive roots ri and ri+1 such that ri < λ* < ri+1, or we find out that one of the roots is λ*. In the latter case we are done and we abort the execution of the generic algorithm. Otherwise, since the sign of a polynomial doesn’t change in between two consecutive roots, we can determine the sign of p(λ*) by evaluating the polynomial p for any value x є (ri ,ri+1). This determines the outcome of the comparison, and, after updating I to I ∩ (ri ,ri+1), we resume the generic execution of AGs. During the execution of AGs, I gets progressively smaller, and we either run AGs to completion, ending up with a final interval I, or we find λ* prematurely and abort the execution of AGs [see fig. 6 & fig. 7 below]. In many applications of parametric search λ* is one of the roots associated with the comparisons, and AGs will never run to completion in these cases. In other cases, such as in the “median-of-lines” example that Megiddo used to explain his technique, the structure of the problem restricted to the final interval I is simple, and the value of λ* can be easily computed, given I. The Graphical Representation of the control flow of algorithm AGs is shown below :

fig.6

fig.7

Running Time: If we denote the running time of As with Ts and the number of comparisons made by As with Cs, then the cost of running parametric search as described above is O(CsTs). This can be improved by computing As(r) only when we really have to : P(λ) is monotonous: if P(λ0) is true, then P(λ) is true for all λ < λ0. Symmetrically, if P(λ0) is false, then P(λ) is false for all λ > λ0. This means that if we can somehow batch k comparisons, we can resolve the associated roots as follows: we find the median λm of the roots using a linear-time median-finding algorithm, and compute As(λm). This determines the outcome of the decision problem for half of the roots, and we recursively deal with the remaining roots. It follows that if the number of roots associated with a comparison is bounded by a constant, we can resolve the k batched comparisons in a binary-search fashion with only O(logk) calls to As. To speed up the execution, Megiddo proposes to replace the generic algorithm by a parallel algorithm Ap. If Ap uses P processors and runs in Tp parallel steps, then each parallel step involves at most P independent comparisons. We can then compute roots of all polynomials associated with these comparisons, and perform a binary search to locate λ* among them using As at each binary step. If As has running time Ts, then the cost of simulating a parallel step of Ap is P(communication cost betn the processors) +Ts log P, for a total of PTp +TpTs log P. In most cases the second term dominates the running time[see fig.8 & fig.9 below].

fig.8

fig.9

RAM Model: There are two optimized algorithms for parametric searching named as COLE’s optimization. One of these algorithms works under the CREW PRAM model of parallel computation, and the constants in the running time are small. However, it does not meet the conditions for applying Cole’s optimization. The other one works under the EREW PRAM model; it is more complex than the first algorithm, but Cole’s optimization can be applied to it.

Some Practical Applications: In practical, there are many applications of parametric searching (specially in geometrical optimization techniques), such as :  spanning tree and scheduling problems studied by Megiddo  the slope-selection problem  the Fr´echet-distance problem  the bottleneck-distance problem  the problem of the minimum Hausdorff distance  the “median-of-lines”-problem  problem of finding the minimum diameter of a set of moving points Here, we will discuss, much briefly, the solution of the “mutual visibility problem among spheres” using parametric searching

Mutual Visibility Problem among Spheres: Let S = {S1,…….., Sn} be a given set of n spheres in R3, all with the same radius. Let ci denote the center of Si, for i = 1,….., n. We say that two spheres Si and Sj are mutually visible if the line segment connecting ci with cj does not intersect any other sphere. We say that S is completely mutually visible if every pair of spheres in S is mutually visible. The problem studied in this section is: “Given a set P of n points in R3, we wish to determine the largest possible common radius r such that the set of n spheres of radius r, centered at the given points, is completely mutually visible." This problem arises in the context of parallel computations using optical interconnections. The spheres model the individual processors, and mutual visibility between a pair of spheres models the ability of the two processors to communicate by an optical link. In our problem the locations of the (centers of the) processors is predetermined, and we want to determine how large can the processors be if every pair is to be able to communicate optically. In order to employ the parametric searching technique, we solve the following fixed-size decision problem: “Given a set of n spheres with the same radius r, determine if it is completely mutually visible". We use the following simple scheme. For each of the spheres Si, we compute the visibility map of all the other spheres, as viewed from its center ci. We then check that all the centers are visible from ci. This is true for each of the n visibility maps, if and only if the set of spheres is completely mutually visible.

The visibility maps can in general have rather high (up to quadratic) combinatorial complexity, but we establish the following interesting property (without proof): Lemma : Let S be a collection of n congruent (nonintersecting) spheres in 3-space, and let p be a point outside the spheres. If the centers of all spheres are visible from p then the complexity of the visibility map of the spheres, as seen from p, is O(n). The idea is now to compute the visibility map of the spheres from each center ci, using the output-sensitive hidden surface removal algorithm. The algorithm runs in time O((n+k) log2 n), where k is the combinatorial complexity of the visibility map. If the algorithm runs for too long, we stop it and conclude, in view of the preceding lemma, that not all centers are visible from ci. Otherwise the algorithm terminates and then we check whether all centers are indeed visible. This takes, over all visible maps, a total time of O(n2 log2 n). In order to apply the parametric search technique, we need a parallel implementation of the hidden surface removal algorithm. Based on the sequential algorithm of hidden surface removal technique, we can develop a parallel algorithm whose running time is O(log2 n) using O(n log n + k) processors. We compute visibility maps from all centers in parallel. We allocate O(n) processors to each center. If any of the procedures require more than the allocated processors, we stop it and conclude that all centers are not mutually visible. If all the visibility maps have linear size, we preprocess each of them for point location queries, and then locate the centers in each of them. This can be done in O(log2 n) using O(n2 log n) processors. We state the final result: Theorem : Given a set of n points in R3, we can find the largest possible common radius r, so that the system of spheres with radius r about the given points are completely mutually visible, in time O(n2 log5 n).

Why Parametric Searching? It is a powerful and ingenious tool for solving efficiently a variety of optimization problems Many problems of this kind, which can be easily attacked by the technique, are either solved by more complicated and more ad-hoc techniques, or are simply left unsolved.

Drawbacks: Parametric-search has always been more popular with theoreticians than with practitioners. While parametric search, when applied to the right problems, often leads to asymptotic running times that are about an order of magnitude better than the alternatives, it is often advised against using the technique in practice. The reason for this negative advice is usually twofold. Firstly, since parametric search is a complicated technique, it is believed that implementing it must also be complicated and hard.

The second reason why parametric search is hardly ever used in practice is that it is generally assumed that the overhead involved (i.e., the hidden constants in the O notation) are too large to be of practical use.

References: [1] P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv.,30:412–458, 1998. [2] M. Ajtai, J. Koml´os, and E. Szemer´edi. Sorting in clogn parallel steps. Combinatorica, 3:1–19, 1983. [3] R. Cole. Parallel merge sort. SIAM J. Comput., 17(4):770–785, 1988. [4] N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 30(4):852–865, 1983. [5] P.K. Agarwal, M. Sharir and S. Toledo, Applications of parametric searching in geometric optimization, manuscript, 1991. [6] M.J. Katz, M.H. Overmars and M. Sharir, Efficient hidden surface removal for objects with small union size, Proc. 7th ACM Symp. on Computational Geometry, 1991, 31-40.