On finding widest empty curved corridorsSergey Bereg∗J. Miguel D´ıaz-B´a˜nez†Carlos Seara‡Inma Ventura§3rd November 2006AbstractAn α-siphon of width w is the locus of points in the plane that are at the same distancew from a 1-corner polygonal chain C such that α is the interior angle of C. Given a set Pof n points in the plane and a fixed angle α , we want to compute the widest empty α-siphonthat splits P into two non-empty sets. We present an efficient O(n log3n)-time algorithm forcomputing the widest oriented α-siphon through P such that the orientation of a half-line ofC is known. We also propose an O(n3log2n)-time algorithm for the widest arbitrarily-orientedversion and an Θ(n log n)-time algorithm for the widest arbitrarily-oriented α-siphon anchoredat a given point.Keywords: Corridors; Geometric optimization; Facility location.1 IntroductionLet P = {p1, p2, . . . , pn} be a set of n points in the plane. A corridor through P is the open regionof the plane bounded by two parallel lines intersecting the convex hull of P , CH(P ). A corridoris empty if it contains no points of P . Houle and Maciel [12] solved the problem of computing thewidest empty corridor through P in O(n2) time (Figure 1(a)). One motivation of the widest emptycorridor problem is to find a collision-free route for transport objects through a set of obstacles(points). However, even the widest empty corridor may be not wide enough. This motivates toallow angle turns. Cheng [1, 2] studied this generalization considering an L-shaped corridor, whichis the concatenation of two perpendicular links (a link is composed by two parallel rays and one linesegment forming an unbounded trapezoid). D´ıaz-B´a˜nez and Hurtado [4] proposed an O(n2)-timealgorithm for locating an obnoxious 1-corner p olygonal chain anchored at two given points.In this paper we study a kind of corridor which we call a siphon that we define next. Let C bea 1-corner polygonal chain consisting of two half-lines emanating from a point v, the corner of C.Let α be the interior angle of C. By d(p, q) we denote the Euclidean distance between two pointsp, q ∈ R2. The distance between p and C is defined asd(p, C) = min{d(p, q) : q ∈ C}.∗Departament of Computer Science, University of Texas at Dallas, Box 830688, Richardson TX 75083, USA,email: [email protected]†Departamento de Matem´atica Aplicada II, Universidad de Sevilla, Camino de los Descubrimientos s/n, 41092Sevilla, Spain, email: [email protected], partially supported by grants BFM2000-1052-C02-01 and BFM2003-04062.‡Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya, 08034 Barcelona, Spain, email:carlos.seara@up c.edu, partially supported by projects DGES-SEUID-PB98-0933, MCYT-FEDER-BFM2002-0557and Gen-Cat-2001SGR00224.§Departamento de Matem´aticas, Universidad de Huelva, Spain, email: [email protected], partially supported bygrants BFM2000-1052-C02-01 and BFM2003-04062.1Definition 1. A siphon is the locus of points in the plane that are at distance w from C, where wis called the siphon width. An α-siphon is a siphon such that the interior angle α of C, the siphonangle, is fixed.An α-siphon is determined by C and w; if α 6= π, it is bounded by an exterior boundary (formedby a circular arc joining two half-lines) and an interior boundary (formed by two half-lines).The widest α-siphon problem. Given a set P of n points in the plane and a fixed value α,0 ≤ α ≤ π, compute the α-siphon with the largest width w such that no points of P lies in itsinterior, and intersects CH(P ) producing a non-trivial bipartition P1, P2, of P (Figure 1(b)).The condition of producing a partition P16= ∅, P26= ∅ of P avoids to obtain an α-siphon“scratching the exterior” of P without actually passing through P and, therefore, being arbitrarilywide (Figure 1c). For any 1-corner polygonal chain C which contains no points of P and producesa non-trivial partition of P , there always exists an α-siphon defined by C. In the sequel, unlessotherwise is specified, we assume that the α-siphon is empty of points...........Yiα..............................................................................................................................................YP1P2www(a)(b) (c) (d)CFigure 1: (a) Corridor, (b) α-siphon, (c) unbounded width siphon, (d) siloNotice that a π-siphon is just a corridor [12] where C is a line (Figure 1(a)). Follert et al. [9]defined a silo as the locus of points in the plane that are at distance w from a ray (Figure 1(d)),they partially studied the problem of computing the widest empty silo for P giving an optimalO(n log n)-time algorithm in the case that the endpoint of ray is anchored at a given point. As faras we know, the non-anchored case is still unsolved. A 0-siphon is not a silo because the non-trivialpartition condition. Follert et al. [9] also solved the corridor problem in O(n log n) time when theaxis of the corridor pass through a given point.The widest α-siphon gives a “better” solution than the L-shaped corridor of Cheng in thefollowing sense: Suppose that we are interesting in transporting a circular object (a disk) withradius w through a set P of obstacles (points), and we ask for the decision problem: Is there a1-corner polygonal path for transporting the disk through P without collision? Cheng’s algorithmcan produces a negative answer while our algorithm gives an affirmative answer; this is so becausethe width of the widest α-siphon is always larger than or equal to the width of the widest L-shapedcorridor. In fact, every L-shaped corridor contains a siphon of the same width and the reciprocalis false (Figure 2). Notice that an α-siphon is the area swept by a disk whose center describes the1-corner polygonal chain C. The siphon shape has been also considered by Glozman et al. in [10]where they studied the problem of covering points with a siphon of smallest width.The widest α-siphon problem belongs to the geometric optimization area in which the placementof a particular kind of empty geometric object of “maximum measure” is considered [3, 5, 7, 16,17, 21]. Some possible applications of the widest α-siphon problem fall into the facility location2Figure 2: The width of the widest α-siphon is larger than the width of the widest L-corridor.area, where the usual goal is to locate an object (facility) within an underlying space such thatsome distance between the facility and the given points
View Full Document
Unlocking...