Rocchio algorithm

2013-09-10T11:41:03Z

134.130.139.106: /* Algorithm */

In [[mathematics]], the '''Schoenflies problem''' or '''Schoenflies theorem''', of [[geometric topology]] is a sharpening of the [[Jordan curve theorem]] by [[Arthur Moritz Schoenflies|Arthur Schoenflies]]. For Jordan curves in the plane it is often referred to as the '''Jordan–Schoenflies theorem.'''

==Original formulation==
It states that not only does every [[simple closed curve]] in the [[plane (mathematics)|plane]] separate the plane into two regions, one (the "inside") [[bounded set|bounded]] and the other (the "outside") unbounded; but also that these two regions are [[homeomorphic]] to the inside and outside of a standard [[circle]] in the plane.

An alternative statement is that if <math>C \subset \mathbb R^2</math> is a simple closed curve, then there is a homeomorphism <math>f : \mathbb R^2 \to \mathbb R^2</math> such that <math>f(C)</math> is the unit [[circle]] in the plane. Elementary proofs can be found in {{harvtxt|Newman|1939}}, {{harvtxt|Cairns|1951}}, {{harvtxt|Moise|1977}} and {{harvtxt|Thomassen|1992}}. If the curve is smooth then the homeomorphism can be chosen to be a diffeomorphism. This can also be deduced from by solving the [[Dirichlet problem]] on the curve (extending results of Kneser, Rado and Choquet); or by showing that the [[Riemann mapping theorem|Riemann mapping]] for the interior of the curve extends smoothly to the boundary, which can be proved either using the Dirichlet problem or [[Bergman kernel]]s.<ref>See:
*{{harvnb|Napier|Ramachandran|2011}}
*{{harvnb|Taylor|2011}}
*{{harvnb|Kerzman|1977}}
*{{harvnb|Bell|Krantz|1987}}
*{{harvnb|Bell|1992}}
</ref>

Such a theorem is only valid in two dimensions. In three dimensions there are [[counterexample]]s such as [[Alexander's horned sphere]]. Although they separate space into two regions, those regions are so twisted and knotted that they are not homeomorphic to the inside and outside of a normal sphere.

==Proofs of the Jordan–Schoenflies theorem==
For smooth or polygonal curves, the [[Jordan curve theorem]] can be proved in a straightforward way. Indeed the curve has a [[tubular neighbourhood]], defined in the smooth case by the field of unit normal vectors to the curve or in the polygonal case by points at a distance of less than ε from the curve.
In a neighbourhood of a differentiable point on the curve, there is a coordinate change in which the curve becomes the diameter of an open disk. Taking a point not on the curve, a straight line aimed at the curve starting at the point will eventually meet the tubular neighborhood; the path can be continued next to the curve until it meets the disk. It will meet it on one side or the other. This proves that the complement of the curve has at most two connected components. On the other hand using the [[Cauchy integral formula]] for the [[winding number]], it can be seen that the winding number is constant on connected components of the complement of the curve, is zero near infinity and increases by 1 when crossing the curve. Hence the curve has exactly two components, its interior and the unbounded component. The same argument works for a piecewise differentiable Jordan curve.<ref>{{harvnb|Katok|Climenhaga|2008}}</ref>

===Polygonal curve===
Given a simple closed polygonal curve in the plane, the '''piecewise linear Jordan–Schoenflies theorem''' states that there is a piecewise linear homeomorphism of the plane, with compact support, carrying the polygon onto a triangle and taking the interior and exterior of one onto the interior and exterior of the other.<ref>See:
*{{harvnb|Moise|1977}}
*{{harvnb|Bing|1983}}
</ref>

The interior of the polygon can be triangulated by small triangles, so that the edges of the polygon from edges of some of the small triangles. Piecewise linear homeomorphisms can be made up from special homeomorphisms obtained by removing a diamond from the plane and taking a piecewise affine map, fixing the edges of the diamond, but moving one diagonal into a V shape. Compositions of homeomorphisms of this kind give rise to piecewise linear homomorphisms of compact support; they fix the outide of a polygon and act in an affine way on a triangulation of the interior.
A simple inductive argument shows that it is always possible to remove a trinangle with one or two sides on the boundary leaving a simple closed Jordan polygon. The special homeomorphisms described above provide piecewise linear homeomorphisms which carry the interior of the larger polygon onto the polygon with the triangle removed. Iterating this process it follows that there is a piecewise linear homeomorphism of compact support carrying the original polygon onto a triangle. The piecewise linear nature of the map will normally require a finer triangulation of the interior of the polygon and triangle to which it maps in order to exhibit the affine maps on smaller triangles.

===Smooth curve===
When the Jordan curve is smooth (parametrized by arc length) the unit normal vectors give a non-vanishing vector field ''X''0 in the tubular neighbourhood ''U''0 of the curve. Take a polygonal curve in the interior of the curve close to the boundary and transverse to the curve (at the vertices the vector field should be strictly within the angle formed by the edges). By the piecewise linear Jordan–Schoenflies theorem, there is a piecewise linear homeomorphism, affine on an appropriate triangulation of the interior of the polygon, taking the polygon onto a triangle. Take an interior point ''P'' in one of the small triangles of the triangulation. It corresponds to a point ''Q'' in the image triangle. There is a radial vector field on the image triangle, formed of straight lines pointing towards ''Q''. This gives a series of lines in the small triangles making up the polygon. Each defines a vector field ''X''''i'' on a neighbourhood ''U''''i'' of the closure of the triangle. Each vector field is transverse to the sides, provided that ''Q'' is chosen in "general position" so that it is not colinear with any of the finitely many edges in the triangulation. On the triangle containing ''P'' the vector field can be taken to be the standard radial vector field. Take a smooth [[partition of unity]] ψ''i'' subordinate to the cover ''U''''i'' and set

:<math>\displaystyle{X=\sum \psi_i\cdot X_i.}</math>

''X'' is a smooth vector field on a neighbourhood of the closure of the interior of the original smooth curve. The integral curves of this vector field go from the points of the curve to the point ''P'' in finite time. Replacing ''X'' by ''f''⋅''X'' for an appropriate smooth positive function ''f'', equal to 1 near the curve and near ''P'', the integral curves will all reach ''P'' at the same time. The properties of the flow associated to ''X'' guarantee that the radial coordinates provided by the integral curves radiating in different directions starting at ''P'' give a diffeomorphism between the [[unit disk]] and the closure of the interior of the curve. The same procedure can be applied to the outside of the curve, after applying a Möbius transformation to map it and ∞ into the finite part of the plane. Applying a translation if necessary, it can be assumed that ''P'' = 0. The two diffeomorphisms with the unit disk patch together to give a smooth diffeomorphism of the Riemann sphere '''R'''2 ∪ ∞ carrying the curve onto the unit circle. It carries the inside and outside of the curve onto the regions |z| < 1 and |z| > 1.

==Generalizations==
There does exist a higher-dimensional generalization due to [[Morton Brown]] and independently [[Barry Mazur]] with [[Marston Morse]], which is also called the generalized '''Schoenflies theorem'''. It states that, if an (''n'' − 1)-dimensional [[sphere]] ''S'' is embedded into the ''n''-dimensional sphere ''Sn'' in a [[locally flat]] way (that is, the embedding extends to that of a thickened sphere), then the pair (''Sn'', ''S'') is homeomorphic to the pair (''Sn'', ''S''''n''−1), where ''S''''n''−1 is the equator of the ''n''-sphere. Brown and Mazur received the [[Veblen Prize]] for their contributions.

The Schoenflies problem can be posed in categories other than the topologically locally flat category, i.e. does a smoothly (piecewise-linearly) embedded (''n'' − 1)-sphere in the ''n''-sphere bound a smooth (piecewise-linear) ''n''-ball? For ''n'' = 4, the problem is still open for both categories. See [[Mazur manifold]]. For ''n'' ≥ 5 the question has an affirmative answer, and follows from the [[h-cobordism]] theorem.

==Notes==
{{reflist|2}}

==References==
*{{citation|last1=Bell|first1= Steven R.|last2= Krantz|first2=Steven G.|title=Smoothness to the boundary of conformal maps|journal=Rocky Mountain J. Math.|volume= 17|year=1987|pages= 23–40}}
*{{citation|last=Bell|first=Steven R.|title= The Cauchy transform, potential theory, and conformal mapping|series= Studies in Advanced Mathematics|publisher= CRC Press|year= 1992|isbn=0-8493-8270-X}}
*{{citation|title=The Geometric Topology of 3-Manifolds|volume =40|series=Colloquium Publications - |publisher=American Mathematical Society|first=R. H.|last= Bing|authorlink=R. H. Bing|year= 1983|isbn=0821810405}}
*[[Morton Brown|Brown, Morton]] (1960), A proof of the generalized Schoenflies theorem. ''Bull. Amer. Math. Soc.'', vol. 66, pp. 74–76. {{MathSciNet| id = 0117695}}
*{{citation|title=An Elementary Proof of the Jordan-Schoenflies Theorem|first=Stewart T.|last=Cairns|journal=Proceedings of the American Mathematical Society|year=1951|pages=860–867}}
*{{citation|last=do Carmo|first= Manfredo P.|title= Differential geometry of curves and surfaces|publisher=Prentice-Hall|year=1976|isbn=0132125897}}
*{{citation|title=Lectures on Surfaces: (Almost) Everything You Wanted to Know about Them|
volume= 46|series= Student Mathematical Library|publisher= American Mathematical Society|first=A. B. |last=Katok|first2= Vaughn|last2= Climenhaga|year= 2008|isbn=0821846795}}
*{{citation|first=N.|last= Kerzman|title= A Monge-Ampére equation in complex analysis|series= Proc. Symp. Pure Math.|volume= XXX|publisher= Am. Math. Soc|year= 1977}}
*Mazur, Barry, On embeddings of spheres., ''Bull. Amer. Math. Soc.'' 65 1959 59–65. {{MathSciNet| id = MR0117693}}
*{{citation|title=Geometric topology in dimensions 2 and 3|volume= 47|series= Graduate texts in mathematics
|first=Edwin E.|last= Moise|publisher=Springer-Verlag|year= 1977|isbn=038790220}}
*Morse, Marston, A reduction of the Schoenflies extension problem., ''Bull. Amer. Math. Soc.'' 66 1960 113–115. {{MathSciNet| id = 0117694}}
*{{citation|title=An Introduction to Riemann Surfaces|first=Terrence|last= Napier|first2= Mohan |last2=Ramachandran|publisher=Springer|year=2011|isbn=0817646922}}
*{{citation|title=Elements of the topology of plane sets of points|first=Maxwell Herman Alexander|last= Newman|publisher= Cambridge University Press|year= 1939}}
*{{citation|last=Taylor|first=Michael E.|authorlink=Michael E. Taylor|title= Partial differential equations I. Basic theory|edition=Second|series=Applied Mathematical Sciences| volume=115|publisher=Springer| year=2011|isbn=978-1-4419-7054-1}}
*{{citation|title=The Jordan-Schoenflies Theorem and the Classification of Surfaces|first=Carsten|last= Thomassen|authorlink=Carsten Thomassen|journal= The American Mathematical Monthly|volume= 99|year= 1992|pages= 116–130}}

[[Category:Geometric topology]]
[[Category:Homeomorphisms]]
[[Category:Theorems in topology]]
[[Category:Mathematical problems]]

formulasearchengine - User contributions [en]

Rocchio algorithm