On finding widest empty curved corridors Sergey Bereg J Miguel D az Ba n ez Carlos Seara Inma Ventura 3rd November 2006 Abstract An siphon of width w is the locus of points in the plane that are at the same distance w from a 1 corner polygonal chain C such that is the interior angle of C Given a set P of n points in the plane and a fixed angle we want to compute the widest empty siphon that splits P into two non empty sets We present an efficient O n log3 n time algorithm for computing the widest oriented siphon through P such that the orientation of a half line of C is known We also propose an O n3 log2 n time algorithm for the widest arbitrarily oriented version and an n log n time algorithm for the widest arbitrarily oriented siphon anchored at a given point Keywords Corridors Geometric optimization Facility location 1 Introduction Let P p1 p2 pn be a set of n points in the plane A corridor through P is the open region of the plane bounded by two parallel lines intersecting the convex hull of P CH P A corridor is empty if it contains no points of P Houle and Maciel 12 solved the problem of computing the widest empty corridor through P in O n2 time Figure 1 a One motivation of the widest empty corridor 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 to allow angle turns Cheng 1 2 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 D az Ba n ez and Hurtado 4 proposed an O n2 time algorithm for locating an obnoxious 1 corner polygonal 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 be a 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 points p q R2 The distance between p and C is defined as d p C min d p q q C Departament of Computer Science University of Texas at Dallas Box 830688 Richardson TX 75083 USA email besp utdallas edu Departamento de Matema tica Aplicada II Universidad de Sevilla Camino de los Descubrimientos s n 41092 Sevilla Spain email dbanez us es partially supported by grants BFM2000 1052 C02 01 and BFM2003 04062 Departament de Matema tica Aplicada II Universitat Polite cnica de Catalunya 08034 Barcelona Spain email carlos seara upc edu partially supported by projects DGES SEUID PB98 0933 MCYT FEDER BFM2002 0557 and Gen Cat 2001SGR00224 Departamento de Matema ticas Universidad de Huelva Spain email iventura us es partially supported by grants BFM2000 1052 C02 01 and BFM2003 04062 1 Definition 1 A siphon is the locus of points in the plane that are at distance w from C where w is called the siphon width An siphon is a siphon such that the interior angle of C the siphon angle is fixed An siphon is determined by C and w if 6 it is bounded by an exterior boundary formed by 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 its interior and intersects CH P producing a non trivial bipartition P1 P2 of P Figure 1 b The condition of producing a partition P1 6 P2 6 of P avoids to obtain an siphon scratching the exterior of P without actually passing through P and therefore being arbitrarily wide Figure 1c For any 1 corner polygonal chain C which contains no points of P and produces a non trivial partition of P there always exists an siphon defined by C In the sequel unless otherwise is specified we assume that the siphon is empty of points w i w Y P1 P2 w Y C a b c d Figure 1 a Corridor b siphon c unbounded width siphon d silo Notice 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 optimal O n log n time algorithm in the case that the endpoint of ray is anchored at a given point As far as we know the non anchored case is still unsolved A 0 siphon is not a silo because the non trivial partition condition Follert et al 9 also solved the corridor problem in O n log n time when the axis of the corridor pass through a given point The widest siphon gives a better solution than the L shaped corridor of Cheng in the following sense Suppose that we are interesting in transporting a circular object a disk with radius w through a set P of obstacles points and we ask for the decision problem Is there a 1 corner polygonal path for transporting the disk through P without collision Cheng s algorithm can produces a negative answer while our algorithm gives 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 every L shaped corridor contains a siphon of the same width and the reciprocal is false Figure 2 Notice that an siphon is the area swept by a disk whose center describes the 1 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 placement of 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 location 2 Figure 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 that some distance between the facility and the given points sites is minimized or maximized see 8 for a recent survey on the current state of art Some of the problems are concerned with finding an undesirable or obnoxious structure just maximizing the smallest distance between the facility and the given points In this sense our problem asks for the …
View Full Document
Unlocking...