The siphon problem

The siphon problem J.M. D´ıaz-B´a˜nez ∗,a,1, C. Seara b,2and I. Ventura a,1 aUniversidad de Sevilla, Spain bUniversitat Polit`ecnica de Catalunya, Spain cUniversidad de Huelva, Spain Abstract An α-siphon is the locus of points in the plane that are at the same distance ǫfrom a polygonal chain consisting of two half-lines emanating from a common point such that αis the interior angle of the half-lines. Given a set Sof npoints in the plane and a fixed angle α, we want to compute an α-siphon of largest width ǫsuch that no points of Slies in its interior. We present an efficient O(n2)-time algorithm for computing an orthogonal siphon. The approach can be handled to solve the problem of the oriented α-siphon for which the orientation of a half-line is known. We also propose an O(n3log n)-time algorithm for the arbitrarily oriented version. 1. Introduction A corridor through a planar point set Sis the open region of the plane that is bounded by two parallel lines intersecting the convex hull of S, CH(S). A corridor is empty if it does not contain any point of S. The problem of computing the widest empty corridor through a set Sof n points in the plane has been solved by Houle and Maciel [3] in O(n2) time (Figure 1a). One of the possible motivations of the widest empty corridor problem is to find a collision-free route to transport objects through a set of point obstacles. However, even the widest empty corridor may not be wide enough sometimes. This motivates to consider allowing right-angle turns. Chen in [1] studied this generalization considering an L-shaped corridor, which is the concatenation of two perpendicular links (a link is composed by two parallel rays and one line segment forming an unbounded trapezoid). ∗Corresponding author Email addresses: [email protected] (J.M. D´ıaz-B´a˜nez), [email protected] (C. Seara), [email protected] (I. Ventura). 1The first author is partially supported by Project MCYT BFM2000-1052-C02-01. 2The second author is partially supported by projects MCYT-FEDER TIC-2001-2171, MCYT-FEDER BFM 2002-0557, Gen Cat 2001SGR00224. In this paper we consider a kind of corridor problem which we call the siphon problem. More precisely, we define a siphon as the locus of points in the plane that are at the same distance ǫfrom a polygonal chain Pconsisting of two half-lines emanating from a common point (a 1-corner polygonal chain). Let αbe the interior angle of the half-lines. An α-siphon is defined similarly but with the constraint that the interior angle of the two half-lines emanating from a common point is α. An α-siphon is determined by Pand ǫ, where ǫ is called the siphon width. Possible values for the siphon angle αare 0◦≤α≤180◦. The α-siphon problem can be stated as follows. α-Siphon problem. Given a set Sof npoints in the plane and a fixed angle α, compute the α-siphon of largest width such that no points p∈Slies in its interior (Figure 1b). The α-siphon has to intersect the convex hull of Sproducing a non-trivial partition S1,S2of S; otherwise we will allow the α-siphon “to scratch the exterior” of Swithout actually passing through Sand, therefore, the α-siphon can be arbitrarily wide (Figure 1c). Notice that a 180◦-siphon is just a corridor [3]. A 0◦-siphon is a silo emanating from a point (the endpoint of a half-line) (Figure 1d) and it has been partially studied in [2] by giving an optimal Θ(nlog n)- time algorithm in the case that the endpoint of the half-line is anchored on a given point. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry . . . . .. . . . . b) P ǫ ❨ ǫ a) ✐ α S1 S2 . . . . .. . . . . c) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . .. . . . . .. . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . ......................ǫ d) ......... ❨ Fig. 1. a) Widest corridor, b) α-siphon c) unbounded width siphon, c) silo Notice also that our α-siphon is a kind of corridor which is a “better” solution than Cheng’s corridor in the following sense: suppose that we are interesting in transporting a circular object in between a set of points, Cheng’s algorithm can gives a negative answer while our algorithm produces an affirmative answer; this is so because the width of the widest α-siphon is always larger than or equal to the width of the widest L-shaped corridor; in fact a siphon is the area swept by a disk whose center describes the route. In this paper two variants for the α-siphon problem are consider: i) the oriented α-siphon problem, where we know the angle αand the direction of one of the half-lines of P; ii) the arbitrarily oriented αsiphon problem, where only the angle αis known. Most proofs are omitted in this extended abstract. Let S={p1, p2,...,pn}be a planar point set. The points are in general position, this assumption is not essential for our algorithms to work, but handling degeneracies would require the description of many details and would hide the crucial ideas. We denote the Euclidean distance between two points pand qby d(p, q). If pis a point and Pis a closed subset in the plane, the distance between pand P is defined as d(p, P) = min{d(p, q) : q∈P}. An α-siphon is bounded by an outer boundary and an inner boundary; the outer boundary is formed by a circular arc joined to two half-lines, the exterior boundary legs; and the inner boundary is formed by two half-lines, the interior boundary legs. By orthogonal siphon we denote an oriented 90◦-siphon such that its boundary legs are vertical and horizontal. 2. Oriented α-siphon In this section we study the problem of computing an oriented α-siphon. First we consider the orthogonal siphon and next we will consider the general case. There are four possibilities for Pin an orthogonal siphon according to the north, south, east and west directions. We only consider the case S-E, other cases can be handle analogously. First notice that for any 1-corner polygonal chain Pwhich does not contain points from S and produces a non-trivial partition of S, always exists a siphon defined by P. We call a siphon non-expansive if its interior boundary contains two points of S(one per each leg or only one point if this point is on the vertex of that boundary) and its exterior boundary contains one point of S. Lemma 1 For any fixed vertical and horizontal lines crossing the convex hull of Sproducing a non trivial partition of S, there exists a non-expansive siphon. Next we describe the algorithm which solves the S-E orthogonal siphon problem in O(n2) time. By Lemma 1 we know that an orthogonal siphon is defined by at most three points. First, the algorithm sorts the points in Sby decreasing y-coordinate and by increasing x-coordinate in O(nlog n) time. Let O={p1,...,pn}and A={q1,...,qn}be the respective lists of the sorted points. From a vertical-horizontal grid we construct a S-E staircase Ewhich is updated each time we insert a new point, and in this case either the number of the steps of Eincrease by one or it decrease because the new point dominates some points of the current E. Let p1and q1be the points of Swith maximum y-coordinate and minimum x-coordinate, respectively. These two points determine the starting point of the algorithm. The staircase Ein the initial stage is formed by the horizontal and vertical half-lines of the grid passing through p1and q1. The algorithm compute all the possible orthogonal siphons which horizontal boundary leg is supported by pi∈O, for i= 2,...,n. If a point pi= (xpi, ypi) is on the horizontal-interior boundary leg of a siphon then, there only exist siphons such that its “entries” are in-between points having x-coordinates and y-coordinates smaller than or equal to xpi and ypi, respectively; because the rest of points either are dominated by either the current staircase or the point pi. The dominance relation between points of Sis establish as in [4,5]. In [5] the maxima problem for a set of points is considered. The maxima problem consists of finding all the maxima of Sunder dominance and they can be computed in θ(nlog n) time. We are interested March 25-26, 2004 Seville (Spain) in the maxima problem with the following dominance relation: pj≺pi⇐⇒ xpj ≤xpi and ypj ≥ ypi.The corresponding set of maxima forms a four quadrant staircase. We construct the staircase Ein an incremental way with a cost of O(log n) time per point insertion. In the worst case the number of different siphons to be checked can be O(n2). Assume that Oand Ahave been computed and also for each point piwe have a pointer to qlsuch that pi=ql. ORTOGONAL-SIPHON-ALGORITHM Input: S,O,A, Output: Widest orthogonal siphon, (i) Initial stage: O,A,E:= staircase formed by the horizontal and vertical half-lines defined by q1and p1. Compute the Voronoi diagram for S,V D(S), and store it in a data structure such that a query point can be answered in O(log n) time. (ii) For i= 2 to n,do “Compute the widest orthogonal siphon supported by piand qj, such that xqj< xpi,yqj< ypi”, Let ǫ1be the distance between y=ypi and the horizontal line containing the segment of the current Ewhich is intersected by x=xqj. Compute ǫ2=xqj −xq(j−1) and ǫ0= min{ǫ1, ǫ2}. The orthogonal siphon supported by piand qjhas width smaller than or equal to ǫ0/2. Compute the part Eij of E in-between the x-coordinates xqj −ǫ0and xqj and the y-coordinates ypi and ypi +ǫ0. Check that Eij is empty and compute the orthogonal siphon of width ǫ0/2 supported by piand qj. Otherwise, we analyze each point of Eij determining (if it exists) the corresponding orthogonal siphon as follows: The vertex of the 1-corner polygonal line of the siphon will be located in the bisector of the second quadrant passing through (xqj, ypi). This vertex is the center of the circle which contains the arc of the siphon. By using Eand V D(S), we consider each of the three possible locations for the point belonging to the exterior boundary. (iii) Updating stage: Insert piin Eand update Ein time O(log n) per insertion and in total time O(nlog n) for the deletion of points from E(a point is deleted only once). Delete pifrom O, delete ql=pifrom A, update the widest width and the current siphon. Lemma 2 Each vertex ciof the staircase Eis analyzed at most once. Analysis of the algorithm: The number of stages is O(n2). At the stage (i, j) we check all the vertices in Eij in O(log n) time. By Lemma 2 a vertex in E is analyzed only once, then the total time cost in the analysis of points in Eis O(nlog n). Therefore the running time of the algorithm is O(nlog n) + O(n2) = O(n2). Theorem 3 The widest orthogonal siphon can be computed in O(n2)time. The techniques above can be adapted for computing the widest oriented α-siphon, i.e., a αsiphon with a given angle α, 0 < α < 180◦and a fixed direction of one of its half-lines. Corollary 4 The widest oriented α-siphon can be computed in O(n2)time. Theorem 5 The problem of computing the widest oriented α-siphon has an Ω(nlog n)time lower bound in the algebraic decision tree model. Notice that the complexity of the algorithm above match the complexity of the algorithm for computing the widest corridor of a set of points. A small variation of the algorithm above can be used to compute the widest L-shaped orthogonal corridor (as defined by Chen [1]) with the same O(n2) running time. Corollary 6 The widest L-shaped orthogonal corridor can be computed in O(n2)time. A similar algorithm can be used if we want to compute a corridor of the same kind but with an angle different from 90◦and knowing the direction of one of the links. 3. The arbitrarily-oriented α-siphon In this section we deal with the computation of a widest-empty arbitrarily-oriented α-siphon, i.e., we only fix the siphon angle α. Assume that αis π 2. Lemma 7 There always exists an optimal π 2- siphon such that the interior boundary contains two points of S(one per each leg) or only one point if this point is on the corner of that boundary. The points in Sthat determine a tentative placement of an optimal α-siphon are called the critical points. Therefore we can classify the cases for critical points according to their location on the parts of the siphon, as it is shown in Figure 2. 20th European Workshop on Computational Geometry (1) (3) (4) (5) (6) (2) Fig. 2. Types of candidate siphons. We sketch the idea of our approach without details. We only consider siphons that are bounded by a point of each its interior half-lines (according to Lemma 7). The orientation θof our siphon is the smaller of the two angles given by the ortogonal lines supporting the interior boundary legs. Given two points pi,pj(xpi> xpj), we consider the rotation of the two perpendicular lines ri(θ) (around pi) and sj(θ) (around pj), say counterclockwise, to obtain all possible empty siphon supported at pi and pj. The essence of our algorithm is to generate a discrete set of subintervals in such rotation and compute a siphon of maximum width for each. We begin the rotation in θ= 0. A pair of orthogonal lines through piand pjpartitions the point set into four disjoint subsets which we label I,II,III and IV (corresponding to the four quadrants). As we change the orientation continuously, the partition survive till some two points become collinear. In fact, by insertion and deletion of the points, we can maintain dynamically each one of the corresponding partition. This spend O(n2) time and space. This produces a partition of the rotation interval. Taking into account the intervals of such partitions for each point pk∈S, we define the following functions: –uk(θ) = d(pk, ri(θ)), for pk∈I, –uk(θ) = d(pk, ri(θ)), lk(θ) = d(pk, sj(θ)) and ck(θ) = d(pk, cijk(θ)), for pk∈II, –lk(θ) = d(pk, sj(θ)), for pk∈III, where cijk(θ) is the center of the circle passing through pktangent to the lines ri(θ) and sj(θ). Lemma 8 Let pkand plbe two distinct points of S. Then, the graphs of two functions corresponding to pkand plintersect at most twice. Let Lbe the lower envelope of the graphs of the functions uk, lkand ck. Lemma 8 implies that the labels of the points corresponding to the edges of L, when we traverse Lfrom left to right, form a Davenport-Schinzel sequence of order two [6]. Therefore, the number of intervals in the partition is O(n) [6], and by using a standard divide-and- conquer approach we can compute Lin O(nlog n) time. Thus, by traversing L, from left to right, we can identify the highest vertex, which corresponds to the optimal direction for the π 2-siphon. In summary, working over all pair of points in S, we have proven the following result. Theorem 9 Given a set Sof npoints in the plane, the widest empty arbitrarily-oriented π 2-siphon can be computed in O(n3log n)time. An adaptation of above approach permits to solve the problem for a fixed angle α, 0◦≤α≤ 180◦in the same time bound. A constrained version of this problem consists into anchoring the vertex of the 1-corner polygonal chain. In this case we obtain the following result. Theorem 10 Given a set Sof npoints in the plane, the widest-empty arbitrarily-oriented anchored α-siphon can be computed in optimal Ω(nlog n)time. References [1] S-W. Chen, Widest empty L-shaped corridor, Information Processing Letters, 58, 1996, pp. 277–283. [2] F. Follert, E. Sch¨omer, J. Sellen, M. Smid, C. Thiel, Computing the largest empty anchored cylinder, and related problems, Inter. Journal of Comput. Geometry and Aplications, Vol. 7 (6), 1997, pp. 563–580. [3] M. E. Houle, A. Maciel, Finding the widest empty corridor through a set of points, in Snapshots of Computational and Discrete Geometry, Godfried Toussaint, ed., Technical Report SOCS-88.11, School of Computer Science, McGill University, 1988. [4] H. T. Kung, F. Luccio, F. P. Preparata, On finding the maxima of a set of vectors, Journal of ACM, 22(4), 1975, pp. 469–476. [5] F. P. Preparata, M. I. Shamos, Computacional Geometry, An introduction, Springer-Verlag, 1988. [6] M. Sharir, P. K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, 1995.