formulasearchengine - User contributions [en]

Log-polar coordinates

2013-12-28T15:12:26Z

75.105.1.121: /* Discrete geometry */ tried to remove the word you every time it was used

In mathematics, a '''rigid transformation''' ([[isometry]]) of a vector space preserves distances between every pair of points.<ref name= Bottema>
{{cite book |title=Theoretical Kinematics |page=reface |url=http://books.google.com/books?id=f8I4yGVi9ocC&printsec=frontcover&dq=kinematics&lr=&as_brr=0&sig=YfoHn9ImufIzAEp5Kl7rEmtYBKc#PPR7,M1 |author=O. Bottema & B. Roth |isbn=0-486-66346-9 |publisher=Dover Publications |year=1990 |nopp=true}}
</ref> <ref name= McCarthy>
{{cite book |title=Introduction to Theoretical Kinematics |page=reface |url=http://www.amazon.com/Introduction-Theoretical-Kinematics-J-McCarthy/dp/0262132524 |author=J. M. McCarthy |isbn=0262132524 |publisher=MIT Press |year=1990 |nopp=true}}
</ref> Rigid transformations of the plane R2, space R3, or real n-dimensional space Rn are termed a '''Euclidean transformation''' because they form the basis of Euclidean geometry.<ref>{{citation|title=Introduction to classical geometries|first1=Ana Irene Ramírez|last1=Galarza|first2=José|last2=Seade|publisher=Birkhauser|year=2007}}.</ref>

The
Rigid transformations include [[rotation (mathematics)|rotations]], [[translation (mathematics)|translations]], [[reflection (mathematics)|reflections]], or their combination. Sometimes reflections are excluded from the definition of a rigid transformation by imposing that the transformation also preserve the [[orientation (mathematics)|handedness]] of figures in the Euclidean space (a reflection would not preserve handedness; for instance, it would transform a left hand into a right hand). To avoid ambiguity, this smaller class of transformations is known as '''proper rigid transformations''' (informally, also known as '''roto-translations'''). In general, any proper rigid transformation can be decomposed as a rotation followed by a translation, while any rigid transformation can be decomposed as an [[improper rotation]] followed by a translation (or as a sequence of reflections).

Any object will keep the same [[shape]] and size after a proper rigid transformation, but not after an improper one.

All rigid transformations are [[affine transformations]]. Rigid transformations which involve a translation are not [[linear transformation]]s. Not all transformations are rigid transformations. An example is a [[shear (mathematics)|shear]], which changes two axes in different ways, or a [[similarity transformation (geometry)|similarity transformation]], which preserves angles but not lengths. The set of all (proper and improper) rigid transformations is a [[group (mathematics)|group]] called the [[Euclidean group]], denoted E(''n'') for ''n''-dimensional Euclidean spaces). The set of proper rigid transformation is called special Euclidean group, denoted SE(''n'').

In [[mechanics]], proper rigid transformations in a 3-dimensional Euclidean space, denoted SE(3), are used to represent the [[Displacement (vector)|linear]] and [[angular displacement]] of [[Rigid body|rigid bodies]].

==Distance formula==
A measure of distance between points, or [[metrics space|metric]], is needed in order to evaluate if a transformation is rigid. The Euclidean distance formula for Rn is the generalization of the Pythagorean theorem. This says the distance squared between two points '''X''' and '''Y''' is the sum of the squares of the distances along the coordinate axes, that is
:<math> d(\mathbf{X},\mathbf{Y})^2 = (X_1-Y_1)^2 + (X_2-Y_2)^2 + \ldots + (X_n-Y_n)^2 = (\mathbf{X}-\mathbf{Y})\cdot(\mathbf{X}-\mathbf{Y}). </math>
where '''X'''=(X1, X2, ..., Xn) and '''Y'''=(Y1, Y2, ..., Yn), and the dot denotes the [[scalar product]].

Using this distance formula, a rigid transformation ''g'':Rn→Rn has the property,
:<math>d(g(\mathbf{X}), g(\mathbf{Y}))^2 = d(\mathbf{X}, \mathbf{Y})^2.</math>

==Translations and Linear Transformations==
A [[translation (geometry)|translation]] of a vector space adds a vector '''d''' to every vector in the space, which means it is the transformation ''g''('''v'''):'''v'''→'''v'''+'''d'''. It is easy to show that this is a rigid transformation by computing,
:<math>d(\mathbf{v}+\mathbf{d},\mathbf{w}+\mathbf{d})^2 = (\mathbf{v}+\mathbf{d} - \mathbf{w}-\mathbf{d})\cdot(\mathbf{v}+\mathbf{d} - \mathbf{w} -\mathbf{d})=(\mathbf{v} - \mathbf{w})\cdot(\mathbf{v}- \mathbf{w}) = d(\mathbf{v},\mathbf{w})^2.</math>

A linear transformation of a vector space, ''L'':Rn→ Rn, has the property that the transformation of a vector, '''V'''=a'''v'''+b'''w''', is the sum of the transformations of its components, that is,
:<math> L(\mathbf{V})=L(a\mathbf{v}+b\mathbf{w})=aL(\mathbf{v})+bL(\mathbf{w}).</math>
Each linear transformation ''L'' can be formulated as a matrix operation, which means ''L'':'''v'''→[L]'''v''', where [L] is an nxn matrix.

A linear transformation is a rigid transformation if it satisfies the condition,
:<math>d([L]\mathbf{v}, [L]\mathbf{w})^2 = d(\mathbf{v},\mathbf{w})^2,</math>
that is
:<math>d([L]\mathbf{v}, [L]\mathbf{w})^2=([L]\mathbf{v}-[L]\mathbf{w})\cdot([L]\mathbf{v}-[L]\mathbf{w})=([L](\mathbf{v}-\mathbf{w}))\cdot([L](\mathbf{v}-\mathbf{w})).</math>
Now use the fact that the scalar product of two vectors '''v'''.'''w''' can be written as the matrix operation '''v'''T'''w''', where the T denotes the matrix transpose, we have
:<math>d([L]\mathbf{v}, [L]\mathbf{w})^2 = (\mathbf{v}-\mathbf{w})^T[L]^T[L](\mathbf{v}-\mathbf{w}).</math>
Thus, the linear transformation ''L'' is rigid if its matrix satisfies the condition
:<math>[L]^T[L]=[I], </math>
where [I] is the identity matrix. Matrices that satisfy this condition are called ''orthogonal matrices.'' This condition actually requires the columns of these matrices to be orthogonal unit vectors.

Matrices that satisfy this condition form a mathematical [[group (mathematics)|group]] under the operation of matrix multiplication called the ''orthogonal group of nxn matrices'' and denoted ''O(n)''.

Compute the determinant of the condition for an [[orthogonal matrix]] to obtain
:<math> \det([L]^T[L]) =\det[L]^2 =\det[I] =1,</math>
which shows that the matrix [L] can have a determinant of either +1 or -1. Orthogonal matrices with determinant -1 are reflections, and those with determinant +1 are rotations. Notice that the set of orthogonal matrices can be viewed as consisting of two manifolds in Rnxn separated by the set of singular matrices.

The set of rotation matrices is called the ''special orthogonal group,'' and denoted ''SO(n).'' It is an example of a [[Lie group]] because it has the structure of a manifold.

== Formal definition ==

A rigid transformation is formally defined as a transformation that, when acting on any vector '''v''', produces a transformed vector ''T''('''v''') of the form
:''T''('''v''') = ''R'' '''v''' + '''t'''
where ''R''T = ''R''−1 (i.e., ''R'' is an [[orthogonal transformation]]), and '''t''' is a vector giving the translation of the origin.

A proper rigid transformation has, in addition,

: [[determinant|det]](R) = 1

which means that ''R'' does not produce a reflection, and hence it represents a [[rotation (mathematics)|rotation]] (an orientation-preserving orthogonal transformation). Indeed, when an orthogonal transformation matrix produces a reflection, its determinant is -1.

==References==
{{Reflist}}

[[Category:Functions and mappings]]

Word wrap

2013-12-08T03:36:38Z

75.105.16.82: /* Word wrapping in text containing Chinese, Japanese, and Korean */

{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|data=[[Array data structure|Array]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time=<math>O(n\log n)</math>
|space=<math>O(n)</math>
|optimal=?
}}
'''Library sort''', or '''gapped insertion sort''' is a [[sorting algorithm]] that uses an [[insertion sort]], but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
<blockquote>Suppose a librarian were to store his books alphabetically on a long shelf, starting with the A's at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Z's. If the librarian acquired a new book that belongs to the B section, once he finds the correct space in the B section, he will have to move every book over, from the middle of the B's all the way down to the Z's in order to make room for the new book. This is an insertion sort. However, if he were to leave a space after every letter, as long as there was still space after B, he would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

The algorithm was proposed by [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>http://arxiv.org/abs/cs/0407003</ref> and published 2006.<ref name="definition">
{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391 | year=2006 | author=Bender, M. A., Farach-Colton, M., and Mosteiro M. | title=Insertion Sort is O(n log n) | doi = 10.1007/s00224-005-1237-z }}</ref>

Like the insertion sort it is based on, library sort is a [[stable sort|stable]] [[comparison sort]] and can be run as an [[online algorithm]]; however, it was shown to have a high probability of running in O(n log n) time (comparable to [[quicksort]]), rather than an insertion sort's O(n2). The mechanism used for this improvement is very similar to that of a [[skip list]]. There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the library sort efficiency compares to other sorting methods in reality.

Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would be implementation dependent. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. One weakness of [[insertion sort]] is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but is also adding an extra cost in the rebalancing step.

==Implementation==

===Algorithm ===
Let us say we have an array of n elements. We choose the gap we intend to
give. Then we would have a final array of size (1 + ε)n. The algorithm works
in log n rounds. In each round we insert as many elements as there are in
the final array already, before re-balancing the array. For finding the position
of inserting, we apply Binary Search in the final array and then swap the
following elements till we hit an empty space. Once the round is over, we
re-balance the final array by inserting spaces between each element.

Following are three important steps of the algorithm:

1. Binary Search:
Finding the position of insertion by applying binary search within the
already inserted elements. This can be done by linearly moving towards
left or right side of the array if you hit an empty space in the middle
element.

2. Insertion:
Inserting the element in the position found and swapping the following
elements by 1 position till an empty space is hit.

3. Re-Balancing:
Inserting spaces between each pair of elements in the array. This takes linear time, and
because there are log n rounds in the algorithm, total re-balancing takes
O(n log n) time only.

===Pseudocode===

'''proc''' rebalance(A, begin, end)
r ← end
w ← end * 2
'''while''' r >= begin
A[w+1] ← gap
A[w] ← A[r]
r ← r - 1
w ← w - 2

'''proc''' sort(A)
n ← length(A)
S ← new array of n gaps
'''for''' i ← 1 to floor(log2(n) + 1)
'''for''' j ← 2^i to 2^(i+1)
ins ← binarysearch(S, 2^(i-1))
insert A[j] at S[ins]

Here, <code>binarysearch(A, k)</code> performs [[binary search]] in the first {{mvar|k}} elements of {{mvar|A}}, skipping over gaps. Insertion should favor gaps over filled-in elements.

== References ==
{{reflist}}

==External links==
*[http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo06-librarysort.pdf Gapped Insertion Sort]

{{sorting}}

[[Category:Sorting algorithms]]
[[Category:Comparison sorts]]
[[Category:Stable sorts]]
[[Category:Online sorts]]