the width of a convex set on the sphere

The width of a convex set on the sphere F.J. Cob os J.C. Dana C.I. Grima A. Marquez Departamento de Matematica Aplicada I Universidad de Sevilla (Spain) e-mail: f cobos|dana|grima|almar g @cica.es Fax: +34-5-4557878 Abstract We study the relationship b etween some alternative denitions of the concept of the width of a convex set on the sphere. Those relations allow to characterize whether a convex set on the sphere can pass through a spherical interval by rigid motions. Finally, we give an optimal algorithm to compute the width on the sphere. Key words: Width, sphere, rigid motions, convex sets. 1 Intro duction In the plane, the width of a nite set of p oints is the minimum distance b etween parallel lines of supp ort of the set [8]. This concept and the computation of the width of a nite set of p oints have applications in several elds such as in rob otic (more sp ecically in collision{ avoidance problems [18]), in approximating p olygonal curves (see [9], [10] and [11]), etc. Moreover, the width of a set is familiar in Operations Research as a minimax lo cation problem, in which we seek a line (the bisector to the lines of supp ort given the width) whose greatest distance to any p oint of the set is a minimum. The denition of the width of a nite set in the plane can b e extended to Euclidean spaces of dimension greater than two. So, if we consider a nite set of p oints P in the space R d , the width of P is the minimum distance b etween parallel hyp erplanes of supp ort of P [8]. As the width of a nite set in the plane is the width of its convex hull [8], many authors have studied the width of convex p olygons, b ecause convex p olygons are simple sets and they have many applications in pattern recognition [1], image pro cessing [14] and sto ck cutting and allo cation (see [5], [16] and [6]). By using the rotating calip er technique [15] or geometric transforms [3] it is p ossible to nd the width of a convex p olygons in linear time and space. We will see that it is p ossible to adapt the rotating calip er technique to design an algorithm for computing the width of a set in the sphere. The study of the width in non-planar surfaces is motived by motion plannig [13], and more concretely a subeld of motion planning of considerable practical interest as it is planning the motion of an articulated rob ot arm, since, as it is well known, in most cases the p oints accessible by them are not, in general, in the plane but in a non{planar surface. G. Strang [17] proved that the width of a convex set in the plane is equivalent to the concept of do or of the set. The do or of a set is the minimum closed interval such that the set can pass through it by a continuous family of rigid motions (translations combined with rotations). Nevertheless, in dimension three this is not true and H. Stark has constructed convex sets which can pass through a do or, either square or circular, although no pro jection of the set will t in the do orway (see [17]). We will see that, with regard to this problem, the b ehavior of the sphere is exactly the same as in the plane. In addition to the problem of the do or of a set, there exist another problems that can 1 b e solved knowing the width of a set. For instance, it is easy to see that the line center (that line minimizing the maximum distance to each p oint of a set) is the median (the equidistance parallel to the a pair of parallels) of the pair of supp ort giving the width. The goal of this pap er is to try to generalize these concepts to convex sets on the sphere and, in addition, to seek necessary and suf- cient conditions that those convex sets may verify to pass through a spherical interval by rigid motions on this surface, and the relationships b etween the concepts describ ed ab ove. These conditions and relationships allow us to design an algorithm which solves the problem of the width of a nite set of p oints on the sphere. Our generalizations will use the concept of convex set on the sphere. We can dene as in [12] that a set C in the sphere is convex if given two p oints of C the minimum geo desic joining these p oints is contained in C . The angular length of a geo desic arc joining the p oints P and Q on the sphere is the angle b etween the two radii joining the center of the sphere with the p oints P and Q resp ectively. Observe that no convex set on the sphere contains a geo desic arc with angular length greater than  2 . 2 Width on the sphere Before trying to generalize the concept of width of a nite set in the plane to the sphere, if we want to give a similar treatment of this idea, we will examine several alternative denitions that are considered in the plane, keeping in mind that we will try to preserve those prop erties when trying the extension to the sphere. So, rstly, we would replace the idea of lines of supp ort of a set by geo desics of supp ort of a set. In this way, if given a convex set C on the sphere, we will call meridians of supp ort of C to the meridians which intersect C and leave the set on one hemisphere. We will call lune of supp ort of C to the region delimited by two meridians of supp ort of C that contains C . As, in the sphere, two dierent meridians have two p oints in common and they dene only one great circle called equator, thus a lune of supp ort denes one equatorial arc. According to these denitions, we can say that, given a convex set C on the sphere, the time width H ( C ) of C is the minimum length b etween the equatorial arcs dened asso ciated to lunes of supp ort of C . The main dierence b etween this denition and the denition of width in the plane is that, in the plane, two parallel lines of supp ort have empty intersection, whereas on the sphere two meridians of supp ort have two p oints in common. If we want to preserve the prop erty that the arcs of supp ort of a convex set have empty intersection, similarly as in the plane, we could give another p ossible denition. Given a convex set C on the sphere, we will call parallel of supp ort of C to a parallel which intersects C and leaves the set on one cap, where a cap is a part of the sphere divided by this parallel. If we use the idea of pair of parallels of supp ort, we will conserve the concept of parallelism that we had in the plane (in the sense that they have empty intersection), but note that parallels in the sphere are not geo desics. According to the denition ab ove, we can say that given a convex set C on the sphere, the tropical width T ( C ) of C is the minimum distance b etween all p ossible pairs of parallels of supp ort of C . Observe, that with this de- nition the tropical width of a set in the sphere can b e used, as in the plane, in Op erations Research as a minimax lo cation problem, in which we seek a great circle (the equator of the parallels of supp ort given the tropical width) whose greatest distance to any p oint of the set is a minimum. On the other hand, and following the pap er of Strang [17] who proved that the width of a convex set in the plane is the minimum length of an closed interval for the set can pass through it by a continuous family of rigid motions, we can give other denitions of width in the sphere as follows, given a convex set C on the sphere, the do or P ( C ) of C is the minimum length b etween all p ossible closed arcs of meridians for the set C can pass through them 2 by continuous family of rigid motions (translations combined with rotations) on the sphere. G. Strang proved that the width of a convex set coincides with its do or in the plane. But, as it was p ointed out in the intro duction, in dimension three this is not true and H. Stark has constructed convex sets which can pass through a do or, either square or circular, although no pro jection of the set will t in the do orway (see [17]. Thus it is interesting to ask if the b ehavior of the sphere is, in this p oint, similar to the plane or to the three dimensional space. In the sphere, we have the following prop erties Lemma 1 Let C be a convex set on the sphere. Then, P ( C )  T ( C ) . Proof: It suces to consider the arc of meridians orthogonal and contained b etween the parallels which dene T ( C ). The length of this arc is greater or equal than P ( C ) and, obviously, less or equal than T ( C ). 2 Lemma 2 Let C be a convex set on the sphere. Then, T ( C )  H ( C ) . Proof: Let H b e the lune that denes H ( C ). This lune is dened by meridian arcs which intersect C in two p oints P and Q . We consider the parallels tangent to C in the p oints P and Q . The distance T  b etween these parallels is equal to H ( C ), so T ( C )  T  = H ( C ). 2 Therefore, P ( C )  T ( C )  H ( C ). Next theorem says, that, as it happ ens in the plane, these three numb ers agree in the sphere. Theorem 3 A convex set C on the sphere can pass through a meridian arc of length P ( C ) if and only if H ( C )  P ( C ) . Proof: If H ( C )  P ( C ) and as C is contained in the lune which its equatorial arc has length H ( C ), obviously C can pass through this equatorial arc by rigid motions. To prove the converse, assume rst that the b oundary @ C of C is smo oth, through every b oundary p oint there is a unique tangent line on the sphere, and it varies continuously along @ C . Let I b e an arc of meridian of length P ( C ) and denote by S the spherical surface. As C can pass through I , it is p ossible to dene a continuous comp osition of motions M : [0 ; 1] ! S where M (0) is the situation of C b efore going into I and M (1) the situation after passing through I . For all t 2 [0 ; 1], we can dene two applications f 1 : [0 ; 1] ! [0 ;  ] and f 2 : [0 ; 1] ! [0 ;  ] as follows: f 1 ( t ) and f 2 ( t ) are the angular lengths b etween the p oints P 1 and P and the p oints P 2 and P resp ectively, where P 1 and P 2 are the intersection of @ C with the arc I and P is the intersection b etween the tangents to C in the p oints P 1 and P 2 (see Figure 1). t t t f 2 ( t ) f 1 ( t ) P P 1 P 2 M ( t ) Figure 1 The application f 1 + f 2 : [0 ; 1] ! [0 ; 2  ] is continuous and f 1 (0) + f 2 (0) = 0 and f 1 (1) + f 2 (1) = 2  , so there exists t  2 [0 ; 1] such that f 1 ( t  ) + f 2 ( t  ) =  . If f 1 ( t  ) = f 2 ( t  ) =  2 , then the meridian arc which denes H ( C ) is contained in I , so H ( C )  P ( C ). Else, f 1 ( t  ) ?  2 =  2 ? f 2 ( t  ). Supp ose that f 1 ( t  ) >  2 and so f 2 ( t  ) <  2 . Then, the situation is as in Figure 2. 3 s s s P 1 P 2 s   = 2  = 2 A B s  ? 9 s s s P 1 A P 2 B  q q  s Figure 2 As the angles in the p oints A and B are of ninety degree, the length of the meridian arc joining P and Q is greater or equal than the length of the meridian arc joining A and B . So, H ( C )  P ( C ) The conclusion remains true for a convex set C even if @ C is not smo oth. We will pro ceed intro ducing a sequence of smo oth convex subsets C n converging to C . As C passes through I so do the C n and their time widths must satisfy H ( C n ) < P ( C ). Therefore, H ( C )  P ( C ) and the theorem is proved. 2 Then, the three denitions of width we have considered agree and we can talk ab out the width of a set. As an immediate consequence of Theorem 3 we get Corollary 4 The minimum equatorial arc of a convex set C is included in C . 3 Algorithm of the width on the sphere Recall, that in the plane the width of a convex p olygon is the minimum distance b etween parallel lines of supp ort passing through an antip o dal vertex-edge pair (to each antip o dal vertex-edge pair, we asso ciated the lune dene by the meridian containing the edge and that containing the vertex such that the equator arc joins the vertex with the edge). In the sphere this is not true and it can b e achieved in an antip o dal edge-edge pair as Figure 3 shows, but we have Lemma 5 The width of a convex polygon is the minimum distance between meridians of support passing through either an antipodal vertex-edge pair or an edge-edge pair. Proof: It is an immediate consequence of Corollary 4. 2 Figure 3 In any case, Lemma 5 says us that it is p ossible to adapt the rotating calip er algorithm to nd the width of a convex p olygon C (the numb er of events is linear). Thus we can give the following algorithm Width( C ) 1.- Find an initial antip o dal vertex-edge pair. 2.- If the asso ciated lune to the vertex-edge pair contains C , compute its equator arc, otherwise compute the equator arc of the pair edge-edge asso ciated to the original vertex-edge pair (this edge-edge pair is dened from the vertex-edge 4 pair by considering the edge incident with the vertex that is not contained in the lune). 3.- Use rotating calip er to generate all pairs as in (1)-(2). 4.- Compute the minimum obtained in previous steps. It is straightforward to check the following result Theorem 6 Algorithm width( C ) computes the width of a convex polygon C in optimal linear time. References [1] S. G. Akl and G. T. Toussaint . Ef- cient convex hull algorithms for pattern recognition applications. Pro c. 4th. Int. Joint Conf. on Pattern Recognition (Kyoto, Japan). 1978, pp. 483{487. [2] J. C. Dana, C. I. Grima and A. M  arquez . Convex hull in non{planar surfaces . 13th Europ ean Workshop on Computational Geometry (CG'97). University of Wuerzburg, Germany. 1997. [3] K. Q. Brown . Geometric transform for fast geometric algorithms . Dep. Comput. Sci., Carnegie{Mellon Univ. 1979. [4] L. Danzer, G. Grunbaum and V. L. Klee . Helly's theorem and its relatives . Pro c. Symp. Pure Math. VI I (Providence, R. I.), American Mathematical So ciety, 1963. [5] H. Freeman . Computer pro cessing of line{drawing images . Comput. Surveys (1974), no. 6, pp. 57{97. [6] H. Freeman and R. Shapira . Determining the minimum{area encasing rectangle for an arbitrary closed curve . Comm. ACM. 18 (1975), no. 7, pp. 409{413. [7] H. Hopf and W. Rinow .  Ub er den Begri der vollstandigen dierentialgeometrischen Flache . Math. Ann. (1931), no. 63, pp. 209{225. [8] M. E. Houle and G. T. Toussaint . Computing the with of a set . IEEE Trans. on pattern analysis and machine intelligence, vol. 10, no. 5, 1988, pp. 761{765. [9] K. Ichida and T. Kiyono . Segmentation of plane curves . Trans. Elec. Commun. Eng., Japan, vol. 58{D, 1975, pp. 689{696. [10] H. Imai and M. Iri . Polygonal approximation of a curve: Formulations and solution algorithms . Computational Morphology. Amsterdam, The Netherlands: North{ Holland, to b e published. [11] Y. Kurozumi and W. A. Davis . Polygonal approximation by the minimax metho d . Comput. Graphics Image Pro cessing, vol. 19, 1982, pp. 248{264. [12] K. Menger . Urtersuchungen ub er allgemeine Metrik . Math. Ann. (1928), no. 100, pp. 75{163. [13] J. O'Rourke . Computational Geometry in C . Cambridge University Press, 1994. [14] A. Rosenfeld . Picture pro cessing by computers . Academic Press, NY. 1969. [15] M. I. Shamos . Computational Geometry . Ph. D. dissertation, Yale Univ. 1978. [16] J. Sklansky . Measuring concavity on a rectangular mosaic . IEEE Trans. Comp. C (1972), no. 21, pp. 1355{1364. [17] G. Strang . The width of a chair . The American Mathematical Monthly, vol. 89, no. 8, 1982 pp. 529{534. [18] G. T. Toussaint . Movable separability of sets . Computational Geometry. Amsterdam, The Netherlands: North{Holland, 1985,pp. 335{375. 5