Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
No edit summary
No edit summary
Line 1: Line 1:
{{hatnote|Not to be confused with [[Positive matrix]] and [[Totally positive matrix]].}}
[[File:Extreme points illustration.png|thumb|right|The convex hull of the red set is the blue [[convex set]].]]
{{See also|Convex set|Convex combination}}
In [[mathematics]], the '''convex hull''' or '''convex envelope''' of a set ''X'' of points in the [[Euclidean plane]] or [[Euclidean space]] is the smallest [[convex set]] that contains ''X''. For instance, when ''X'' is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around ''X''.<ref name="rubber band">{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, p. 3.</ref>


In [[linear algebra]], a [[symmetric matrix|symmetric]] {{nowrap|''n'' &times; ''n''}} [[real number|real]] [[matrix (mathematics)|matrix]] ''M'' is said to be '''positive definite''' if ''z''<sup>T</sup>''Mz'' is positive for every non-zero column [[vector (mathematics)|vector]] ''z'' of ''n'' real numbers. Here ''z''<sup>T</sup> denotes the [[transpose]] of ''z''.
Formally, the convex hull may be defined as the intersection of all convex sets containing ''X'' or as the set of all [[convex combination]]s of points in&nbsp;''X''. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary [[real vector space]]s; they may also be generalized further, to [[oriented matroid]]s.{{sfnp|Knuth|1992}}


More generally, an {{nowrap|''n'' × ''n''}} [[Hermitian matrix]] ''M'' is said to be '''positive definite''' if ''z*Mz'' is real and positive for all non-zero column vectors ''z'' of ''n'' complex numbers. Here ''z*'' denotes the [[conjugate transpose]] of ''z''.
The [[algorithm]]ic problem of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces is one of the fundamental problems of [[computational geometry]].


The '''negative definite''', '''positive semi-definite''', and '''negative semi-definite''' matrices are defined in the same way, except that the expression ''z''<sup>T</sup>''Mz'' or ''z*Mz'' is required to be always negative, non-negative, and non-positive, respectively.
==Definitions==
A set of points is defined to be [[convex set|convex]] if it contains the line segments connecting each pair of its points. The convex hull of a given set ''X'' may be defined as
#The (unique) minimal convex set containing ''X''
#The intersection of all convex sets containing ''X''
#The set of all [[convex combination]]s of points in ''X''.
#The union of all [[simplex|simplices]] with vertices in ''X''.


Positive definite matrices are closely related to [[definite bilinear form|positive-definite]] symmetric [[bilinear form]]s (or [[sesquilinear form]]s in the complex case), and to [[inner product]]s of vector spaces.<ref>[http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.rmjm/1250130219&page=record Stewart, J. (1976). Positive definite functions and generalizations, an historical survey. Rocky Mountain J. Math, 6(3).]</ref>
It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing ''X'', for every ''X''? However, the second definition, the intersection of all convex sets containing ''X'' is well-defined, and it is a subset of every other convex set ''Y'' that contains ''X'', because ''Y'' is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing ''X''. Each convex set containing ''X'' must (by the assumption that it is convex) contain all convex combinations of points in ''X'', so the set of all convex combinations is contained in the intersection of all convex sets containing ''X''. Conversely, the set of all convex combinations is itself a convex set containing ''X'', so it also contains the intersection of all convex sets containing ''X'', and therefore the sets given by these two definitions must be equal.
In fact, according to [[Carathéodory's theorem (convex hull)|Carathéodory's theorem]], if ''X'' is a subset of an ''N''-dimensional vector space, convex combinations of at most ''N''&nbsp;+&nbsp;1 points are sufficient in the definition above. Therefore, the convex hull of a set ''X'' of three or more points in the plane is the union of all the [[triangle]]s determined by triples of points from ''X'', and more generally in ''N''-dimensional space the convex hull is the union of the [[simplex|simplices]] determined by at most ''N''&nbsp;+&nbsp;1 vertices from X.


Some authors use more general definitions of "positive definite" that include some non-symmetric real matrices, or non-Hermitian complex ones.
If the convex hull of ''X'' is a [[closed set]] (as happens, for instance, if ''X'' is a [[finite set]] or more generally a [[compact set]]), then it is the intersection of all closed [[Half-space (geometry)|half-space]]s containing ''X''. The [[hyperplane separation theorem]] proves that in this case, each point not in the convex hull can be separated from the convex hull by a half-space. However, there exist convex sets, and convex hulls of sets, that cannot be represented in this way. One example is an open halfspace together with a single point on its boundary.


== Examples ==
More abstractly, the convex-hull operator Conv() has the characteristic properties of a [[closure operator]]:
*It is ''extensive'', meaning that the convex hull of every set ''X'' is a superset of ''X''.
*It is ''[[Monotone_function#Monotonicity_in_order_theory|non-decreasing]]'', meaning that, for every two sets ''X'' and ''Y'' with ''X''&nbsp;⊆&nbsp;''Y'', the convex hull of ''X'' is a subset of the convex hull of&nbsp;''Y''.
*It is ''[[idempotence|idempotent]]'', meaning that for every ''X'', the convex hull of the convex hull of ''X'' is the same as the convex hull of&nbsp;''X''.


*The [[identity matrix]] <math> I = \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} </math> is positive definite. Seen as a real matrix, it is symmetric, and, for any non-zero column vector ''z'' with real entries ''a'' and ''b'', one has <math> z^{\mathrm{T}}I z = \begin{bmatrix} a & b\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} \begin{bmatrix} a \\ b\end{bmatrix}= a^2 + b^2</math>. Seen as a complex matrix, for any non-zero column vector ''z'' with complex entries ''a'' and ''b'' one has <math> z^*I z = \begin{bmatrix} a^* & b^*\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} \begin{bmatrix} a \\ b\end{bmatrix}=a^*a +b^*b = |a|^2 + |b|^2</math>.  Either way, the result is positive since ''z'' is not the zero vector (that is, at least one of ''a'' and ''b'' is not zero).
==Convex hull of a finite point set==
[[File:Convex hull.png|thumb|Convex hull of some points in the plane]]


* The real symmetric matrix
The convex hull of a [[finite set|finite]] point set <math>S</math> is the set of all [[convex combination]]s of its points. In a convex combination, each point <math>x_i</math> in <math>S</math> is assigned a weight or coefficient <math>\alpha_i</math> in such a way that the coefficients are all non-negative and sum to one,  and these weights are used to compute a [[weighted average]] of the points. For each choice of coefficients, the resulting convex combination is a point in the convex hull, and the whole convex hull can be formed by choosing coefficients in all possible ways. Expressing this as a single formula, the convex hull is the set:
:<math>\left\{\sum_{i=1}^{|S|} \alpha_i x_i \mathrel{\Bigg|} (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{|S|} \alpha_i=1 \right\}.</math>


::<math> M = \begin{bmatrix} 2&-1&0\\-1&2&-1\\0&-1&2 \end{bmatrix} </math>  
The convex hull of a finite point set <math>S \in \mathbb{R}^n</math> forms a [[convex polygon]] when ''n'' = 2, or more generally a [[convex polytope]] in <math>\mathbb{R}^n</math>. Each point <math>x_i</math> in <math>S</math> that is not in the convex hull of the other points (that is, such that <math>x_i\notin\operatorname{Conv}(S\setminus\{x_i\})</math>) is called a [[Vertex (geometry)|vertex]] of <math>\operatorname{Conv}(S)</math>. In fact, every convex polytope in <math>\mathbb{R}^n</math> is the convex hull of its vertices.
:is positive definite since for any non-zero column vector ''z'' with entries ''a'', ''b'' and ''c'', we have
::<math>\begin{align} z^{\mathrm{T}}M z = (z^{\mathrm{T}}M) z &= \begin{bmatrix} (2a-b)&(-a+2b-c)&(-b+2c) \end{bmatrix} \begin{bmatrix} a\\b\\c \end{bmatrix} \\
&= 2{a}^2 - 2ab + 2{b}^2 - 2bc + 2{c}^2 \\
&= {a}^2+(a - b)^{2} + (b - c)^{2}+{c}^2
\end{align} </math>
:This result is a sum of squares, and therefore non-negative; and is zero only if ''a'' = ''b'' = ''c'' = 0, that is, when ''z'' is zero.


*The real symmetric matrix
[[File:ConvexHull.svg|thumb|Convex hull of a finite set: elastic-band analogy]]
If the points of <math>S</math> are all on a [[Line (geometry)|line]], the convex hull is the [[line segment]] joining the outermost two points.
When the set <math>S</math> is a [[empty set|nonempty]] [[finite set|finite subset]] of the [[Euclidean geometry|plane]] (that is, [[two-dimensional]]), we may imagine stretching a [[rubber band]] so that it surrounds the entire set <math>S</math> and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of <math>S</math>.<ref name="rubber band"/>


::<math>N =  \begin{bmatrix} 1 & 2 \\ 2 & 1\end{bmatrix} </math>
In two dimensions, the convex hull is sometimes partitioned into two polygonal chains, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for points in any dimension in general position, each [[Facet (geometry)|facet]] of the convex hull is either oriented upwards (separating the hull from points directly above it) or downwards; the union of the upward-facing facets forms a topological disk, the upper hull, and similarly the union of the downward-facing facets forms the lower hull.<ref>{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, p. 6. The idea of partitioning the hull into two chains comes from an efficient variant of [[Graham scan]] by {{harvtxt|Andrew|1979}}.</ref>
:is not positive definite. If ''z'' is the vector <math>\begin{bmatrix} 1\\ -1\end{bmatrix}</math>, one has <math> z^{\mathrm{T}}N z = \begin{bmatrix} 1 & -1\end{bmatrix} \begin{bmatrix} 1 & 2 \\ 2 & 1\end{bmatrix} \begin{bmatrix} 1 \\ -1\end{bmatrix}=\begin{bmatrix} -1 & 1\end{bmatrix} \begin{bmatrix} 1 \\ -1\end{bmatrix}=-2 \not > 0.</math>


*For any real non-singular matrix <math>A</math>, the product <math> A^T A </math> is a positive definite matrix. A simple proof is that for any non-zero vector <math> z </math>, the condition <math> z^T A^T A z = \| A z \|_2^2 > 0, </math> since the non-singularity of matrix <math>A</math> means that <math>Az \neq 0.</math>
==Computation of convex hulls==
{{Main|Convex hull algorithms}}


The examples ''M'' and ''N'' above show that a matrix in which some elements are negative may still be positive-definite, and conversely a matrix whose entries are all positive may not be positive definite.
In computational geometry, a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects.


==Connections==
Computing the convex hull means constructing an unambiguous, efficient [[data structure|representation]] of the required convex shape. The complexity of the corresponding algorithms is usually estimated in terms  of '''''n''''', the number of input points, and '''''h''''', the number of points on the convex hull.
The general purely [[quadratic form|quadratic real function]] ''f''(''z'') on ''n'' real variables ''z''<sub>1</sub>, ..., ''z<sub>n</sub>'' can always be written as ''z''<sup>T</sup>''Mz'' where ''z'' is the column vector with those variables, and ''M'' is a symmetric real matrix.  Therefore, the matrix being positive definite means that ''f'' has a unique minimum (zero) when ''z'' is zero, and is strictly positive for any other ''z''.


More generally, a twice-differentiable real function ''f'' on ''n'' real variables has an isolated local minimum at arguments ''z''<sub>1</sub>, ..., ''z<sub>n</sub>'' if its [[gradient]] is zero and its [[Hessian matrix|Hessian]] (the matrix of all second derivatives) is positive definite at that point.  Similar statements can be made for negative definite and semi-definite matrices.
For points in two and three dimensions, [[output-sensitive algorithm]]s are known that compute the convex hull in time O(''n''&nbsp;log&nbsp;''h''). For dimensions&nbsp;''d'' higher than 3, the time for computing the convex hull is <math>O(n^{\lfloor d/2\rfloor})</math>, matching the worst-case output complexity of the problem.{{sfnp|Chazelle|1993}}


In [[statistics]], the [[covariance matrix]] of a [[multivariate probability distribution]] is always positive semi-definite; and it is positive definite unless one variable is an exact linear combination of the others. Conversely, every positive semi-definite matrix is the covariance matrix of some multivariate distribution.
==Minkowski addition and convex hulls==
{{See also|Minkowski addition|Shapley–Folkman lemma}}
[[File:Minkowski sum.png|thumb|alt=Three squares are shown in the nonnegative quadrant of the Cartesian plane. The square Q<sub>1</sub>=[0,1]×[0,1] is green. The square Q<sub>2</sub>=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q<sub>1</sub>+Q<sub>2</sub>=[1,3]×[1,3].|[[Minkowski addition]] of sets. The <!-- [[Minkowski addition|Minkowski]]&nbsp; -->[[sumset|sum]] of the squares&nbsp;Q<sub>1</sub>=[0,1]<sup>2</sup> and&nbsp;Q<sub>2</sub>=[1,2]<sup>2</sup> is the square&nbsp;Q<sub>1</sub>+Q<sub>2</sub>=[1,3]<sup>2</sup>.]]


== Characterizations ==
The operation of taking convex hulls behaves well with respect to the Minkowski addition of sets.
Let ''M'' be an ''n'' × ''n'' [[Hermitian matrix]]. The following properties are equivalent to ''M'' being positive definite:
* In a real vector-space, the ''[[Minkowski addition|Minkowski&nbsp;sum]]'' of two (non-empty) sets&nbsp;S<sub>1</sub> and&nbsp;S<sub>2</sub> is defined to be the [[sumset|set]] S<sub>1</sub>&nbsp;+&nbsp;S<sub>2</sub> formed by the addition of vectors element-wise from the summand-sets
#'''All its [[eigenvalues]] are positive.'''  Let ''P''<sup>−1</sup>''DP'' be an [[eigendecomposition of a matrix|eigendecomposition]] of ''M'', where ''P'' is a [[unitary matrix|unitary complex matrix]] whose rows comprise an [[orthonormal basis]] of [[eigenvector]]s of ''M'', and ''D'' is a ''real'' [[diagonal matrix]] whose [[main diagonal]] contains the corresponding [[eigenvalue]]s. The matrix ''M'' may be regarded as a diagonal matrix ''D'' that has been re-expressed in coordinates of the basis ''P''. In particular, the one-to-one change of variable ''y'' = ''Pz'' shows that ''z*Mz'' is real and positive for any complex vector ''z'' if and only if ''y*Dy'' is real and positive for any ''y''; in other words, if ''D'' is positive definite. For a diagonal matrix, this is true only if each element of the main diagonal—that is, every eigenvalue of  ''M''—is positive. Since the [[spectral theorem]] guarantees all eigenvalues of a Hermitian matrix to be real, the positivity of eigenvalues can be checked using [[Descartes' rule of signs|Descartes' rule of alternating signs]] when the [[characteristic polynomial]] of a real, symmetric matrix ''M'' is available.
: S<sub>1</sub>&nbsp;+&nbsp;S<sub>2</sub> = { ''x<sub>1</sub>''&nbsp;+&nbsp;''x<sub>2</sub>'' : ''x<sub>1</sub>''&nbsp;∈&nbsp;S<sub>1</sub> and ''x<sub>2</sub>''&nbsp;∈&nbsp;S<sub>2</sub> }.
#'''The associated sesquilinear form is an inner product.''' The [[sesquilinear form]] defined by ''M'' is the function <math>\langle \cdot,\cdot\rangle</math> from '''C'''<sup>''n''</sup> × '''C'''<sup>''n''</sup> to '''C''' such that <math>\langle x,y\rangle := y^*M x</math> for all ''x'' and ''y'' in '''C'''<sup>''n''</sup>, where ''y<sup>*</sup>'' is the complex conjugate of ''y''. For any complex matrix ''M'', this form is linear in each argument separately.  Therefore the form is an [[inner product]] on '''C'''<sup>''n''</sup> if and only if <math>\langle z,z\rangle</math> is real and positive for all nonzero ''z''; that is if and only if ''M'' is positive definite. (In fact, every inner product on '''C'''<sup>''n''</sup> arises in this fashion from a Hermitian positive definite matrix.)
More generally, the ''Minkowski&nbsp;sum'' of a finite&nbsp;family of (non-empty) sets&nbsp;S<sub>n</sub> is <!-- defined to be --> the set <!-- of vectors --> formed by element-wise addition of vectors<!-- from the summand-sets -->
# '''It is the Gram matrix of linearly independent vectors.''' Let <math>x_1,\ldots,x_n</math> be a list of ''n'' [[linearly independent]] vectors of some [[complex vector space]] with an inner product <math>\langle \cdot,\cdot\rangle</math>. It can be verified that the [[Gram matrix]] ''M'' of those vectors, defined by <math>M_{ij} = \langle x_i, x_j\rangle</math>, is always positive definite.  Conversely, if ''M'' is positive definite, it has an eigendecomposition ''P''<sup>−1</sup>''DP'' where ''P'' is unitary, ''D'' diagonal, and all diagonal elements D<sub>''ii''</sub> = λ<sub>''i''</sub> of ''D'' are real and positive. Let ''E'' be the real diagonal matrix with entries <math> E_{ii} = \sqrt{\lambda_i} </math> so <math> E^2 = D </math>; then <math> P^{-1}DP = P^*DP = P^*E E P = (EP)^* EP. </math> Now we let <math>x_1,\ldots,x_n</math> be the columns of ''EP''.  These vectors are linearly independent, and by the above ''M'' is their Gram matrix, under the standard inner product of '''C'''<sup>''n''</sup>, namely <math>\langle x_i, x_j\rangle = x_i^* x_j</math>
: ∑&nbsp;S<sub>n</sub> = { ∑&nbsp;''x<sub>n</sub>'' : ''x<sub>n</sub>''&nbsp;∈&nbsp;S<sub>n</sub> }.
# '''Its leading principal minors are all positive.''' The ''k''th [[minor (linear algebra)|leading principal minor]] of a matrix ''M'' is the [[determinant]] of its upper-left ''k'' by ''k'' sub-matrix.  It turns out that a matrix is positive definite if and only if all these determinants are positive. This condition is known as [[Sylvester's criterion]], and provides an efficient test of positive-definiteness of a symmetric real matrix. Namely, the matrix is reduced to an [[upper triangular matrix]] by using [[elementary row operations]], as in the first part of the [[Gaussian elimination]] method, taking care to preserve the sign of its determinant during [[pivot element|pivoting]] process.  Since the ''k''th leading principal minor of a triangular matrix is the product of its diagonal elements up to row ''k'', Sylvester's criterion is equivalent to checking whether its diagonal elements are all positive. This condition can be checked each time a new row ''k'' of the triangular matrix is obtained.
#'''It has a unique Cholesky decomposition.''' The matrix ''M'' is positive definite if and only if there exists a unique lower triangular matrix ''L'', with real and strictly positive diagonal elements, such that ''M'' = ''LL*''. This factorization is called the [[Cholesky decomposition]] of ''M''.


==Quadratic forms==
<!-- For Minkowski&nbsp;addition, the ''zero set''&nbsp;{0} containing only the [[null vector|zero&nbsp;vector]]&nbsp;0 has [[identity element|special importance]]: For every non-empty subset&nbsp;S of a vector space
The (purely) [[quadratic form]] associated with a real matrix ''M'' is the function ''Q'' : '''R'''<sup>''n''</sup> → '''R''' such that ''Q''(''x'') = ''x''<sup>T</sup>''Mx'' for all ''x''. It turns out that the matrix ''M'' is positive definite if and only if it is symmetric and its quadratic form is a [[strictly convex function]].
: S&nbsp;+&nbsp;{0} = S;
in algebraic terminology, the zero&nbsp;vector&nbsp;0 is the [[identity element]] of Minkowski addition (on the collection of non-empty sets).<ref>
The [[empty set]] is important in Minkowski addition, because the empty&nbsp;set annihilates every other subset: For every  subset&nbsp;S of a vector space, its sum with the empty set is empty
: S+∅ = ∅.
</ref> -->
* For all subsets&nbsp;S<sub>1</sub> and&nbsp;S<sub>2</sub> of a real vector-space, the convex hull of their Minkowski&nbsp;sum is the Minkowski&nbsp;sum of their convex hulls
: Conv(&nbsp;S<sub>1</sub>&nbsp;+&nbsp;S<sub>2</sub>&nbsp;) = Conv(&nbsp;S<sub>1</sub>&nbsp;) + Conv(&nbsp;S<sub>2</sub>&nbsp;).
This result holds more generally for each finite&nbsp;collection of non-empty sets
: Conv(&nbsp;&nbsp;∑&nbsp;S<sub>n</sub> &nbsp;) = ∑&nbsp;Conv(&nbsp;S<sub>n</sub>&nbsp;).
In other words, the [[operation (mathematics)|operation]]s of Minkowski&nbsp;summation and of forming convex hulls are [[commutativity|commuting]] operations.<ref>{{harvtxt|Krein|Šmulian|1940}}, Theorem&nbsp;3, pages&nbsp;562–563.</ref><ref name="Schneider">For the commutativity of [[Minkowski sum|Minkowski addition]] and convexification, see Theorem&nbsp;1.1.2 (pages&nbsp;2–3) in {{harvtxt|Schneider|1993}}; this reference discusses much of the literature on the convex hulls of [[Minkowski addition|Minkowski]] [[sumset]]s in its "Chapter&nbsp;3 Minkowski addition" (pages&nbsp;126–196).</ref>


More generally, any [[quadratic function]] from '''R'''<sup>''n''</sup> to '''R''' can be written as ''x''<sup>T</sup>''Mx'' + ''x''<sup>T</sup>''b'' + ''c'' where ''M'' is a symmetric ''n'' × ''n'' matrix, ''b'' is a real ''n''-vector, and ''c'' a real constant.  This quadratic function is strictly convex when ''M'' is positive definite, and hence has a unique finite global minimum, if and only if ''M'' is positive definite. For this reason, positive definite matrices play an important role in [[optimization (mathematics)|optimization]] problems.
These results show that ''Minkowski addition'' differs from the [[union (set theory)|''union ''operation]] of [[set theory]]; indeed, the union of two convex&nbsp;sets need ''not'' be convex: The [[subset|inclusion]]  Conv(S)&nbsp;∪&nbsp;Conv(T)&nbsp;⊆&nbsp;Conv(S&nbsp;∪&nbsp;T) is generally strict. The convex-hull operation is needed for the set of convex sets to form a <!-- complete  -->[[lattice (order)|lattice]], in which the [[join and meet|"''join''" operation]] is the convex hull of the union of two convex sets
: Conv(S)∨Conv(T) = Conv( S&nbsp;∪&nbsp;T ) = Conv(&nbsp;Conv(S)&nbsp;∪&nbsp;Conv(T)&nbsp;).


== Simultaneous diagonalization ==
== Relations to other structures ==


A symmetric, and a symmetric and positive-definite matrix can be simultaneously diagonalized, although not necessarily via a [[Matrix similarity|similarity transformation]]. This result does not extend to the case of three or more matrices. In this section we write for the real case. Extension to the complex case is immediate.
The [[Delaunay triangulation]] of a point set and its [[dual (mathematics)|dual]], the [[Voronoi Diagram]], are mathematically  related to convex hulls: the Delaunay triangulation of a point set in '''R'''<sup>''n''</sup> can be viewed as the projection of a convex hull in '''R'''<sup>''n''+1</sup>.{{sfnp|Brown|1979}}


Let ''M'' be a symmetric and ''N'' a symmetric and positive-definite matrix. Write the generalized eigenvalue equation as (''M''−λ''N'')''x'' = 0 where we impose that ''x'' be normalized, i.e. ''x''<sup>T</sup>''Nx'' = 1. Now we use [[Cholesky decomposition]] to write the inverse of ''N'' as ''Q''<sup>T</sup>''Q''. Multiplying by ''Q'' and ''Q''<sup>T</sup>, we get ''Q''(''M''−λ''N'')''Q''<sup>T</sup>''x'' = 0, which can be rewritten as (''QMQ''<sup>T</sup>)''y'' = λ''y'' where ''y''<sup>T</sup>''y'' = 1. Manipulation now yields ''MX'' = ''NX''Λ where ''X'' is a matrix having as columns the generalized eigenvectors and Λ is a diagonal  matrix with the generalized eigenvalues.  Now premultiplication with ''X''<sup>T</sup> gives the final result: ''X''<sup>T</sup>''MX'' = Λ and ''X''<sup>T</sup>''NX'' = ''I'', but note that this is no longer an orthogonal diagonalization.
Topologically, the convex hull of an [[open set]] is always itself open, and the convex hull of a [[compact set]] is always itself compact; however, there exist closed sets for which the convex hull is not closed.<ref>{{harvtxt|Grünbaum|2003}}, p. 16.</ref> For instance, the closed set
:<math>\left\{(x,y)\mid y\ge \frac{1}{1+x^2}\right\}</math>
has the open [[upper half-plane]] as its convex hull.


Note that this result does not contradict what is said on simultaneous diagonalization in the article [[Diagonalizable matrix#Simultaneous diagonalization|Diagonalizable matrix]], which refers to simultaneous diagonalization by a similarity transformation. Our result here is more akin to a simultaneous diagonalization of two quadratic forms, and is useful for optimization of one form under conditions on the other. For this result see Horn&Johnson, 1985, page 218 and following.
== Applications ==
The problem of finding convex hulls finds its practical applications in [[pattern recognition]], [[image processing]], [[statistics]], [[GIS]] and [[static code analysis]] by [[abstract interpretation]]. It also serves as a tool, a building block for a number of other computational-geometric algorithms such as the [[rotating calipers]] method for computing the [[width]] and [[diameter]] of a point set.


== Negative-definite, semidefinite and indefinite matrices ==<!-- [[Positive-semidefinite matrix]] and [[Positive semi-definite matrix]] redirect here -->
==See also==
A [[Hermitian matrix]] is negative-definite, negative-semidefinite, or positive-semidefinite if and only if all of its [[eigenvalues]] are negative, non-positive, or non-negative, respectively.
* [[Affine hull]]
* [[Linear hull]]
* [[Krein–Milman theorem]]
* [[Choquet theory]]
* [[Holomorphically convex hull]]
* [[Orthogonal convex hull]]
* [[Oloid]]
* [[Helly's theorem]]
* [[Alpha shape]]
==Notes==
{{reflist}}


=== Negative-definite ===
==References==
*{{citation
| last = Andrew | first = A. M.
| doi = 10.1016/0020-0190(79)90072-3
| issue = 5
| journal = Information Processing Letters
| pages = 216–219
| title = Another efficient algorithm for convex hulls in two dimensions
| volume = 9
| year = 1979}}.
*{{citation
| last = Brown | first = K. Q.
| doi = 10.1016/0020-0190(79)90074-7
| issue = 5
| journal = Information Processing Letters
| pages = 223–228
| title = Voronoi diagrams from convex hulls
| volume = 9
| year = 1979}}.
*{{citation
| last1 = de Berg | first1 = M.
| last2 = van Kreveld | first2 = M.
| last3 = Overmars | first3 = Mark | author3-link = Mark Overmars
| last4 = Schwarzkopf | first4 = O.
| pages = 2–8
| publisher = Springer
| title = Computational Geometry: Algorithms and Applications
| year = 2000
| url=http://books.google.com/books?hl=sv&lr=&id=tkyG8W2163YC&oi=fnd&pg=PA2}}.
*{{citation|first=Bernard|last=Chazelle|author-link=Bernard Chazelle|title=An optimal convex hull algorithm in any fixed dimension|journal=[[Discrete and Computational Geometry]]|volume=10|issue=1|pages=377–409|year=1993|doi=10.1007/BF02573985|url=http://www.cs.princeton.edu/~chazelle/pubs/ConvexHullAlgorithm.pdf}}.
*{{citation|title=Convex Polytopes|series=Graduate Texts in Mathematics|first=Branko|last=Grünbaum|authorlink=Branko Grünbaum|edition=2nd|publisher=Springer|year=2003|isbn=9780387004242}}.
*{{citation
| last = Knuth | first = Donald E. | author-link = Donald Knuth
| doi = 10.1007/3-540-55611-7
| isbn = 3-540-55611-7
| location = Heidelberg
| mr = 1226891
| page = ix+109
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Axioms and hulls
| url = http://www-cs-faculty.stanford.edu/~uno/aah.html
| volume = 606
| year = 1992}}.
*{{citation|first1=M.|last1=Krein|authorlink1=Mark Krein|first2=V.|last2=Šmulian|year=1940|title=On regularly convex sets in the space conjugate to a Banach space|journal=Annals of Mathematics|series=2nd ser.|volume=41|pages=556–583|jstor=1968735|doi=10.2307/1968735|mr=2009}}.
*{{citation|last=Schneider|first=Rolf|title=Convex bodies: The Brunn–Minkowski theory|series=Encyclopedia of Mathematics and its Applications|volume=44|publisher=Cambridge&nbsp;University Press|location=Cambridge|year=1993|isbn=0-521-35220-7|mr=1216521}}.


The {{nowrap|''n'' &times; ''n''}} Hermitian matrix ''M'' is said to be ''negative-definite'' if
==External links==
{{wikibooks|Algorithm Implementation|Geometry/Convex hull|Convex hull}}
* {{MathWorld | urlname=ConvexHull | title=Convex Hull}}
* [http://demonstrations.wolfram.com/ConvexHull/ "Convex Hull"] by [[Eric W. Weisstein]], [[Wolfram Demonstrations Project]], 2007.


:<math>x^{*} M x < 0\,</math><!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->
[[Category:Closure operators]]
 
[[Category:Convex hulls]]
for all non-zero ''x'' in '''C'''<sup>''n''</sup> (or, all non-zero ''x'' in '''R'''<sup>''n''</sup> for the real matrix), where ''x*'' is the [[conjugate transpose]] of ''x''.
[[Category:Convex analysis]]
 
[[Category:Computational geometry]]
A matrix is negative definite if its ''k''th order leading principal minor is negative when ''k'' is odd, and positive when ''k'' is even.
 
=== Positive-semidefinite ===
M is called ''positive-semidefinite'' (or sometimes ''nonnegative-definite'') if
 
:<math>x^{*} M x \geq 0</math>
 
for all ''x'' in '''C'''<sup>''n''</sup> (or, all ''x'' in '''R'''<sup>''n''</sup> for the real matrix).
 
A matrix ''M'' is positive-semidefinite if and only if it arises as the [[Gram matrix]] of some set of vectors.  In contrast to the positive-definite case, these vectors need not be linearly independent.
 
For any matrix ''A'', the matrix ''A*A'' is positive semidefinite, and rank(''A'')&nbsp;= rank(''A*A''). 
Conversely, any Hermitian positive semi-definite matrix ''M'' can be written as ''M''&nbsp;= ''LL*'', where ''L'' is lower triangular; this is the [[Cholesky decomposition]].  If ''M'' is not positive definite, then some of the diagonal elements of ''L'' may be zero.
 
A Hermitian matrix is positive semidefinite if and only if all of its principal minors are nonnegative. It is however not enough to consider the leading principal minors only, as is checked on the diagonal matrix with entries 0 and -1.
 
=== Negative-semidefinite ===
It is called ''negative-semidefinite'' if
 
:<math>x^{*} M x \leq 0</math>
 
for all ''x'' in '''C'''<sup>''n''</sup> (or, all ''x'' in '''R'''<sup>''n''</sup> for the real matrix).
 
=== Indefinite ===
A Hermitian matrix which is neither positive definite, negative definite, positive-semidefinite, nor negative-semidefinite is called ''indefinite''. Indefinite matrices are also characterized by having both positive and negative eigenvalues.
 
== Further properties ==
If ''M'' is a Hermitian positive-semidefinite matrix, one sometimes writes ''M''&nbsp;≥&nbsp;0 and if ''M'' is positive-definite one writes ''M''&nbsp;>&nbsp;0.<ref>This may be confusing, as sometimes [[nonnegative matrix|nonnegative matrices]] are also denoted in this way.  A common alternative notation is <math>M \succeq 0</math> and <math> M \succ 0</math> for positive semidefinite and positive definite matrices, respectively.</ref> The notion comes from [[functional analysis]] where positive-semidefinite matrices define [[positive operator]]s.
 
For arbitrary square matrices ''M'', ''N'' we write ''M''&nbsp;≥&nbsp;''N'' if ''M''&nbsp;−&nbsp;''N''&nbsp;≥&nbsp;0; i.e., ''M''&nbsp;−&nbsp;''N'' is positive semi-definite.  This defines a [[partially ordered set|partial ordering]] on the set of all square matrices.  One can similarly define a strict partial ordering ''M''&nbsp;>&nbsp;''N''.
 
# Every positive definite matrix is [[invertible matrix|invertible]] and its inverse is also positive definite.<ref>{{harvtxt|Horn|Johnson|1985}}, p. 397</ref> If ''M''&nbsp;≥&nbsp;''N''&nbsp;>&nbsp;0 then ''N''<sup>−1</sup>&nbsp;≥&nbsp;''M''<sup>−1</sup>&nbsp;>&nbsp;0, and {{sqrt|''M''}} > {{sqrt|''N''}} &nbsp;>&nbsp;0.<ref>{{harvtxt|Horn|Johnson|1985}}, Corollary 7.7.4(a)</ref> Moreover, by the [[min-max theorem]], the ''k''th largest eigenvalue of ''M'' is greater than the ''k''th largest eigenvalue of ''N''
# If ''M'' is positive definite and ''r''&nbsp;>&nbsp;0 is a real number, then ''rM'' is positive definite.<ref name="HJobs713">{{harvtxt|Horn|Johnson|1985}}, Observation 7.1.3</ref> If ''M'' and ''N'' are positive definite, then the sum ''M''&nbsp;+&nbsp;''N''<ref name="HJobs713"/> and the products ''MNM'' and ''NMN'' are also positive definite. If ''MN''&nbsp;=&nbsp;''NM'', then ''MN'' is also positive definite.
# Every principal submatrix of a positive definite matrix is positive definite.
# ''Q<sup>T</sup> M Q''  is non-negative definite. If ''Q'' is invertible, then ''Q<sup>T</sup> M Q'' is positive definite. Note that ''Q<sup>-1</sup> M Q'' need not to be positive definite.
# The determinant of ''M'' is bounded by the product of its diagonal elements.
# The diagonal entries ''m<sub>ii</sub>'' are real and non-negative. As a consequence the [[trace (linear algebra)|trace]], tr(''M'')&nbsp;≥&nbsp;0. Furthermore,<ref>{{harvtxt|Horn|Johnson|1985}}, p. 398</ref> since every principal sub matrix (in particular, 2-by-2) is positive definite,
#::<math>|m_{ij}| \leq \sqrt{m_{ii}m_{jj}} \leq \frac{m_{ii}+m_{jj}}{2}</math>
#:and thus
#::<math> \max |m_{ij}| \leq \max|m_{ii}|</math>
# A matrix ''M'' is positive semi-definite if and only if there is a positive semi-definite matrix ''B'' with ''B''<sup>2</sup>&nbsp;=&nbsp;''M''. This matrix ''B'' is unique,<ref>{{harvtxt|Horn|Johnson|1985}}, Theorem 7.2.6 with ''k'' = 2</ref> is called the [[square root of a matrix|square root]] of ''M'', and is denoted with ''B''&nbsp;=&nbsp;''M''<sup>1/2</sup> (the square root ''B'' is not to be confused with the matrix ''L'' in the [[Cholesky factorization]] ''M'' = ''LL*'', which is also sometimes called the square root of ''M''). If ''M''&nbsp;>&nbsp;''N''&nbsp;>&nbsp;0 then ''M''<sup>1/2</sup>&nbsp;>&nbsp;''N''<sup>1/2</sup>&nbsp;>&nbsp;0.
# If ''M'' is a symmetric matrix of the form ''m<sub>ij</sub>'' = ''m''(''i''−''j''), and the ''strict'' inequality holds
#::<math>\sum\nolimits_{j\neq 0}|m(j)|< m(0)</math>
#:then ''M'' is ''strictly'' positive definite.
# Let ''M''&nbsp;>&nbsp;0 and ''N'' Hermitian. If ''MN''&nbsp;+&nbsp;''NM''&nbsp;≥&nbsp;0 (resp., ''MN''&nbsp;+&nbsp;''NM''&nbsp;>&nbsp;0) then ''N''&nbsp;≥&nbsp;0 (resp., ''N''&nbsp;>&nbsp;0).{{citation needed|date=November 2010}}
# If ''M''&nbsp;>&nbsp;0 is real, then there is a δ&nbsp;>&nbsp;0 such that ''M''&nbsp;>&nbsp;δI, where ''I'' is the [[identity matrix]].
# If ''M<sub>k</sub>'' denotes the leading ''k'' by ''k'' minor, <math> \det(M_k)/\det(M_{k-1}) </math> is the ''k''th pivot during [[LU decomposition]].
# The set of positive semidefinite symmetric matrices is [[convex set|convex]].  That is, if ''M'' and ''N'' are positive semidefinite, then for any α between 0 and 1, α''M'' + (1−α)''N'' is also positive semidefinite.  For any vector ''x'':
#:: <math>  x^\top (\alpha M + (1-\alpha) N ) x = \alpha x^\top  M x + (1-\alpha) x^\top N  x \geq 0. </math>
#:This property guarantees that [[semidefinite programming]] problems converge to a globally optimal solution.
# If ''M,N''&nbsp;≥&nbsp;0, although ''MN'' is not necessary positive-semidefinite, the [[Kronecker product]] ''M''&nbsp;⊗&nbsp;''N''&nbsp;≥&nbsp;0, the [[Hadamard product (matrices)|Hadamard product]] ''M''&nbsp;○&nbsp;''N''&nbsp;≥&nbsp;0 (this result is often called the [[Schur product theorem]]).,<ref>{{harvtxt|Horn|Johnson|1985}}, Theorem 7.5.3</ref> and the [[Matrix multiplication#Frobenius product|Frobenius product]] ''M''&nbsp;:&nbsp;''N''&nbsp;≥&nbsp;0 (Lancaster-Tismenetsky, The Theory of Matrices, p.&nbsp;218).
# Regarding the Hadamard product of two positive-semidefinite matrices ''M''&nbsp;=&nbsp;(''m<sub>ij</sub>'')&nbsp;≥&nbsp;0, ''N''&nbsp;≥&nbsp;0, there are two notable inequalities:
#*Oppenheim's inequality: <math>\det(M \circ N) \geq \det (N) \prod\nolimits_{i} m_{ii}.</math><ref>{{harvtxt|Horn|Johnson|1985}}, Theorem 7.8.6</ref>
#*det(''M''&nbsp;○&nbsp;''N'') ≥ det(''M'') det(''N'').<ref name=styan1973>{{Harvard citations | last=Styan | year=1973}}</ref>
 
== Block matrices ==
A positive 2''n'' × 2''n'' matrix may also be defined by [[block matrix|blocks]]:
 
:<math> M =  \begin{bmatrix} A & B \\ C & D \end{bmatrix} </math>
 
where each block is ''n'' × ''n''. By applying the positivity condition, it immediately follows that ''A'' and ''D'' are hermitian, and ''C'' = ''B*''.
 
We have that ''z*Mz'' ≥ 0 for all complex ''z'', and in particular for ''z'' = ( ''v'', 0)<sup>T</sup>. Then
 
:<math> \begin{bmatrix} v^* & 0  \end{bmatrix} \begin{bmatrix} A & B \\ B^* & D \end{bmatrix} \begin{bmatrix} v \\ 0 \end{bmatrix} = v^* A v \ge 0. </math>
 
A similar argument can be applied to ''D'', and thus we conclude that both ''A'' and ''D'' must be positive definite matrices, as well.
 
Converse results can be proved with stronger conditions on the blocks, for instance using the [[Schur complement#Schur complement condition for positive definiteness|Schur complement]].
 
== On the definition ==
 
===Consistency between real and complex definitions===
Since every real matrix is also a complex matrix, the definitions of "positive definite" for the two classes must agree.
 
For complex matrices, the most common definition says that "''M'' is positive definite if and only if ''z*Mz'' is real and positive for all non-zero ''complex'' column vectors ''z''".  This condition implies that ''M'' is Hermitian, that is, its transpose is equal to its conjugate. To see this, consider the matrices ''A'' = (''M''+''M*'')/2 and ''B'' = (''M''−''M*'')/(2''i''), so that ''M'' = ''A''+''iB'' and  ''z*Mz'' = ''z*Az'' + ''iz*Bz''.  The matrices ''A'' and ''B'' are Hermitian, therefore ''z*Az'' and ''z*Bz'' are individually real. If ''z*Mz'' is real, then ''z*Bz'' must be zero for all ''z''.  Then ''B'' is the zero matrix and ''M'' = ''A'', proving that ''M'' is Hermitian.
 
By this definition, a positive definite ''real'' matrix ''M'' is Hermitian, hence symmetric; and ''z''<sup>T</sup>''Mz'' is positive for all non-zero ''real'' column vectors ''z''".  However the last condition alone is not sufficient for ''M'' to be positive definite. For example, if
 
:<math>M = \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix},</math>
 
then for any real vector ''z'' with entries ''a'' and ''b'' we have ''z''<sup>T</sup>''Mz'' = (''a''−''b'')''a'' + (''a''+''b'')''b'' = ''a''<sup>2</sup> + ''b''<sup>2</sup>, which is always positive if ''z'' is not zero. However, if ''z'' is the complex vector with entries 1 and ''i'', one gets
 
:''z*Mz'' = [1, −''i'']''M''[1, ''i'']<sup>T</sup> = [1+''i'', 1−''i''][1, ''i'']<sup>T</sup> = 2 + 2''i'',
 
which is not real. Therefore, ''M'' is not positive definite.
 
On the other hand, for a ''symmetric'' real matrix ''M'', the condition "''z''<sup>T</sup>''Mz'' > 0 for all nonzero real vectors ''z''" ''does'' imply that ''M'' is positive definite in the complex sense.
 
===Extension for non symmetric matrices===
Some authors choose to say that a complex matrix ''M'' is positive definite if Re(''z*Mz'') > 0 for all non-zero complex vectors ''z'', where Re(''c'') denotes the real part of a complex number ''c''.<ref name="mathw">Weisstein, Eric W. ''[http://mathworld.wolfram.com/PositiveDefiniteMatrix.html Positive Definite Matrix.]'' From ''MathWorld--A Wolfram Web Resource''. Accessed on 2012-07-26</ref>  This weaker definition encompasses some non-Hermitian complex matrices, including some non-symmetric real ones, such as <math> \bigl[ \begin{smallmatrix} 1 & 1 \\ -1 & 1 \end{smallmatrix} \bigr] </math>.
 
Indeed, with this definition, a real matrix is positive definite if and only if ''z''<sup>T</sup>''Mz'' > 0 for all nonzero real vectors ''z'', even if ''M'' is not symmetric.
 
In general, we have Re(''z*Mz'') > 0 for all complex nonzero vectors ''z'' if and only if the Hermitian part (''M'' + ''M*'')/2 of ''M'' is positive definite in the narrower sense.  Similarly, we have ''x''<sup>T</sup>''Mx'' > 0 for all real nonzero vectors ''x'' if and only if the symmetric part (''M'' + ''M''<sup>T</sup>)/2 of ''M'' is positive definite in the narrower sense.
 
In summary, the distinguishing feature between the real and complex case is that, a [[Bounded operator|bounded]] positive operator on a complex Hilbert space is necessarily Hermitian, or self adjoint. The general claim can be argued using the [[polarization identity]]. That is no longer true in the real case.
 
== See also ==
*[[Cholesky decomposition]]
*[[Covariance matrix]]
*[[M-matrix]]
*[[Positive-definite function]]
*[[Positive-definite kernel]]
*[[Schur complement]]
*[[Square root of a matrix]]
*[[Sylvester's criterion]]
 
== Notes ==
{{Reflist}}
 
== References ==
* {{Citation | last1=Horn | first1=Roger A. | last2=Johnson | first2=Charles R. | title=Matrix Analysis | publisher=[[Cambridge University Press]] | isbn=978-0-521-38632-6 | year=1990}}.
* [[Rajendra Bhatia]]. ''Positive definite matrices''. Princeton Series in Applied Mathematics, 2007. ISBN 978-0-691-12918-1.
 
== External links ==
* {{springer|title=Positive-definite form|id=p/p073880}}
* [http://mathworld.wolfram.com/PositiveDefiniteMatrix.html Wolfram MathWorld: Positive Definite Matrix]
 
{{DEFAULTSORT:Positive-Definite Matrix}}
[[Category:Matrices]]
 
[[de:Definitheit#Definitheit von Matrizen]]

Revision as of 08:56, 9 August 2014

The convex hull of the red set is the blue convex set.

DTZ's public sale group in Singapore auctions all forms of residential, workplace and retail properties, outlets, homes, lodges, boarding homes, industrial buildings and development websites. Auctions are at present held as soon as a month.

We will not only get you a property at a rock-backside price but also in an space that you've got longed for. You simply must chill out back after giving us the accountability. We will assure you 100% satisfaction. Since we now have been working in the Singapore actual property market for a very long time, we know the place you may get the best property at the right price. You will also be extremely benefited by choosing us, as we may even let you know about the precise time to invest in the Singapore actual property market.

The Hexacube is offering new ec launch singapore business property for sale Singapore investors want to contemplate. Residents of the realm will likely appreciate that they'll customize the business area that they wish to purchase as properly. This venture represents one of the crucial expansive buildings offered in Singapore up to now. Many investors will possible want to try how they will customise the property that they do determine to buy by means of here. This location has offered folks the prospect that they should understand extra about how this course of can work as well.

Singapore has been beckoning to traders ever since the value of properties in Singapore started sky rocketing just a few years again. Many businesses have their places of work in Singapore and prefer to own their own workplace area within the country once they decide to have a everlasting office. Rentals in Singapore in the corporate sector can make sense for some time until a business has discovered a agency footing. Finding Commercial Property Singapore takes a variety of time and effort but might be very rewarding in the long term.

is changing into a rising pattern among Singaporeans as the standard of living is increasing over time and more Singaporeans have abundance of capital to invest on properties. Investing in the personal properties in Singapore I would like to applaud you for arising with such a book which covers the secrets and techniques and tips of among the profitable Singapore property buyers. I believe many novice investors will profit quite a bit from studying and making use of some of the tips shared by the gurus." – Woo Chee Hoe Special bonus for consumers of Secrets of Singapore Property Gurus Actually, I can't consider one other resource on the market that teaches you all the points above about Singapore property at such a low value. Can you? Condominium For Sale (D09) – Yong An Park For Lease

In 12 months 2013, c ommercial retails, shoebox residences and mass market properties continued to be the celebrities of the property market. Models are snapped up in report time and at document breaking prices. Builders are having fun with overwhelming demand and patrons need more. We feel that these segments of the property market are booming is a repercussion of the property cooling measures no.6 and no. 7. With additional buyer's stamp responsibility imposed on residential properties, buyers change their focus to commercial and industrial properties. I imagine every property purchasers need their property funding to understand in value. In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.[1]

Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary real vector spaces; they may also be generalized further, to oriented matroids.Template:Sfnp

The algorithmic problem of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces is one of the fundamental problems of computational geometry.

Definitions

A set of points is defined to be convex if it contains the line segments connecting each pair of its points. The convex hull of a given set X may be defined as

  1. The (unique) minimal convex set containing X
  2. The intersection of all convex sets containing X
  3. The set of all convex combinations of points in X.
  4. The union of all simplices with vertices in X.

It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing X, for every X? However, the second definition, the intersection of all convex sets containing X is well-defined, and it is a subset of every other convex set Y that contains X, because Y is included among the sets being intersected. Thus, it is exactly the unique minimal convex set containing X. Each convex set containing X must (by the assumption that it is convex) contain all convex combinations of points in X, so the set of all convex combinations is contained in the intersection of all convex sets containing X. Conversely, the set of all convex combinations is itself a convex set containing X, so it also contains the intersection of all convex sets containing X, and therefore the sets given by these two definitions must be equal. In fact, according to Carathéodory's theorem, if X is a subset of an N-dimensional vector space, convex combinations of at most N + 1 points are sufficient in the definition above. Therefore, the convex hull of a set X of three or more points in the plane is the union of all the triangles determined by triples of points from X, and more generally in N-dimensional space the convex hull is the union of the simplices determined by at most N + 1 vertices from X.

If the convex hull of X is a closed set (as happens, for instance, if X is a finite set or more generally a compact set), then it is the intersection of all closed half-spaces containing X. The hyperplane separation theorem proves that in this case, each point not in the convex hull can be separated from the convex hull by a half-space. However, there exist convex sets, and convex hulls of sets, that cannot be represented in this way. One example is an open halfspace together with a single point on its boundary.

More abstractly, the convex-hull operator Conv() has the characteristic properties of a closure operator:

  • It is extensive, meaning that the convex hull of every set X is a superset of X.
  • It is non-decreasing, meaning that, for every two sets X and Y with X ⊆ Y, the convex hull of X is a subset of the convex hull of Y.
  • It is idempotent, meaning that for every X, the convex hull of the convex hull of X is the same as the convex hull of X.

Convex hull of a finite point set

Convex hull of some points in the plane

The convex hull of a finite point set is the set of all convex combinations of its points. In a convex combination, each point in is assigned a weight or coefficient in such a way that the coefficients are all non-negative and sum to one, and these weights are used to compute a weighted average of the points. For each choice of coefficients, the resulting convex combination is a point in the convex hull, and the whole convex hull can be formed by choosing coefficients in all possible ways. Expressing this as a single formula, the convex hull is the set:

The convex hull of a finite point set forms a convex polygon when n = 2, or more generally a convex polytope in . Each point in that is not in the convex hull of the other points (that is, such that ) is called a vertex of . In fact, every convex polytope in is the convex hull of its vertices.

Convex hull of a finite set: elastic-band analogy

If the points of are all on a line, the convex hull is the line segment joining the outermost two points. When the set is a nonempty finite subset of the plane (that is, two-dimensional), we may imagine stretching a rubber band so that it surrounds the entire set and then releasing it, allowing it to contract; when it becomes taut, it encloses the convex hull of .[1]

In two dimensions, the convex hull is sometimes partitioned into two polygonal chains, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for points in any dimension in general position, each facet of the convex hull is either oriented upwards (separating the hull from points directly above it) or downwards; the union of the upward-facing facets forms a topological disk, the upper hull, and similarly the union of the downward-facing facets forms the lower hull.[2]

Computation of convex hulls

Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.

In computational geometry, a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects.

Computing the convex hull means constructing an unambiguous, efficient representation of the required convex shape. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.

For points in two and three dimensions, output-sensitive algorithms are known that compute the convex hull in time O(n log h). For dimensions d higher than 3, the time for computing the convex hull is , matching the worst-case output complexity of the problem.Template:Sfnp

Minkowski addition and convex hulls

DTZ's public sale group in Singapore auctions all forms of residential, workplace and retail properties, outlets, homes, lodges, boarding homes, industrial buildings and development websites. Auctions are at present held as soon as a month.

We will not only get you a property at a rock-backside price but also in an space that you've got longed for. You simply must chill out back after giving us the accountability. We will assure you 100% satisfaction. Since we now have been working in the Singapore actual property market for a very long time, we know the place you may get the best property at the right price. You will also be extremely benefited by choosing us, as we may even let you know about the precise time to invest in the Singapore actual property market.

The Hexacube is offering new ec launch singapore business property for sale Singapore investors want to contemplate. Residents of the realm will likely appreciate that they'll customize the business area that they wish to purchase as properly. This venture represents one of the crucial expansive buildings offered in Singapore up to now. Many investors will possible want to try how they will customise the property that they do determine to buy by means of here. This location has offered folks the prospect that they should understand extra about how this course of can work as well.

Singapore has been beckoning to traders ever since the value of properties in Singapore started sky rocketing just a few years again. Many businesses have their places of work in Singapore and prefer to own their own workplace area within the country once they decide to have a everlasting office. Rentals in Singapore in the corporate sector can make sense for some time until a business has discovered a agency footing. Finding Commercial Property Singapore takes a variety of time and effort but might be very rewarding in the long term.

is changing into a rising pattern among Singaporeans as the standard of living is increasing over time and more Singaporeans have abundance of capital to invest on properties. Investing in the personal properties in Singapore I would like to applaud you for arising with such a book which covers the secrets and techniques and tips of among the profitable Singapore property buyers. I believe many novice investors will profit quite a bit from studying and making use of some of the tips shared by the gurus." – Woo Chee Hoe Special bonus for consumers of Secrets of Singapore Property Gurus Actually, I can't consider one other resource on the market that teaches you all the points above about Singapore property at such a low value. Can you? Condominium For Sale (D09) – Yong An Park For Lease

In 12 months 2013, c ommercial retails, shoebox residences and mass market properties continued to be the celebrities of the property market. Models are snapped up in report time and at document breaking prices. Builders are having fun with overwhelming demand and patrons need more. We feel that these segments of the property market are booming is a repercussion of the property cooling measures no.6 and no. 7. With additional buyer's stamp responsibility imposed on residential properties, buyers change their focus to commercial and industrial properties. I imagine every property purchasers need their property funding to understand in value.

Three squares are shown in the nonnegative quadrant of the Cartesian plane. The square Q1=[0,1]×[0,1] is green. The square Q2=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q1+Q2=[1,3]×[1,3].
Minkowski addition of sets. The sum of the squares Q1=[0,1]2 and Q2=[1,2]2 is the square Q1+Q2=[1,3]2.

The operation of taking convex hulls behaves well with respect to the Minkowski addition of sets.

  • In a real vector-space, the Minkowski sum of two (non-empty) sets S1 and S2 is defined to be the set S1 + S2 formed by the addition of vectors element-wise from the summand-sets
S1 + S2 = { x1 + x2 : x1 ∈ S1 and x2 ∈ S2 }.

More generally, the Minkowski sum of a finite family of (non-empty) sets Sn is the set formed by element-wise addition of vectors

∑ Sn = { ∑ xn : xn ∈ Sn }.
  • For all subsets S1 and S2 of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls
Conv( S1 + S2 ) = Conv( S1 ) + Conv( S2 ).

This result holds more generally for each finite collection of non-empty sets

Conv(  ∑ Sn  ) = ∑ Conv( Sn ).

In other words, the operations of Minkowski summation and of forming convex hulls are commuting operations.[3][4]

These results show that Minkowski addition differs from the union operation of set theory; indeed, the union of two convex sets need not be convex: The inclusion Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) is generally strict. The convex-hull operation is needed for the set of convex sets to form a lattice, in which the "join" operation is the convex hull of the union of two convex sets

Conv(S)∨Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).

Relations to other structures

The Delaunay triangulation of a point set and its dual, the Voronoi Diagram, are mathematically related to convex hulls: the Delaunay triangulation of a point set in Rn can be viewed as the projection of a convex hull in Rn+1.Template:Sfnp

Topologically, the convex hull of an open set is always itself open, and the convex hull of a compact set is always itself compact; however, there exist closed sets for which the convex hull is not closed.[5] For instance, the closed set

has the open upper half-plane as its convex hull.

Applications

The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics, GIS and static code analysis by abstract interpretation. It also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.

See also

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.

External links

DTZ's auction group in Singapore auctions all types of residential, workplace and retail properties, retailers, homes, accommodations, boarding houses, industrial buildings and development websites. Auctions are at the moment held as soon as a month.

Whitehaven @ Pasir Panjang – A boutique improvement nicely nestled peacefully in serene Pasir Panjang personal estate presenting a hundred and twenty rare freehold private apartments tastefully designed by the famend Ong & Ong Architect. Only a short drive away from Science Park and NUS Campus, Jade Residences, a recent Freehold condominium which offers high quality lifestyle with wonderful facilities and conveniences proper at its door steps. Its fashionable linear architectural fashion promotes peace and tranquility living nestled within the D19 personal housing enclave. Rising workplace sector leads real estate market efficiency, while prime retail and enterprise park segments moderate and residential sector continues in decline International Market Perspectives - 1st Quarter 2014

There are a lot of websites out there stating to be one of the best seek for propertycondominiumhouse, and likewise some ways to discover a low cost propertycondominiumhouse. Owning a propertycondominiumhouse in Singapore is the dream of virtually all individuals in Singapore, It is likely one of the large choice we make in a lifetime. Even if you happen to're new to Property listing singapore funding, we are right here that will help you in making the best resolution to purchase a propertycondominiumhouse at the least expensive value.

Jun 18 ROCHESTER in MIXED USE IMPROVEMENT $1338000 / 1br - 861ft² - (THE ROCHESTER CLOSE TO NORTH BUONA VISTA RD) pic real property - by broker Jun 18 MIXED USE IMPROVEMENT @ ROCHESTER @ ROCHESTER PK $1880000 / 1br - 1281ft² - (ROCHESTER CLOSE TO NORTH BUONA VISTA) pic real estate - by broker Tue 17 Jun Jun 17 Sunny Artwork Deco Gem Near Seashore-Super Deal!!! $103600 / 2br - 980ft² - (Ventnor) pic actual estate - by owner Jun 17 Freehold semi-d for rent (Jalan Rebana ) $7000000 / 5909ft² - (Jalan Rebana ) actual property - by dealer Jun sixteen Ascent @ 456 in D12 (456 Balestier Highway,Singapore) pic real property - by proprietor Jun 16 RETAIL SHOP AT SIM LIM SQUARE FOR SALE, IT MALL, ROCHOR, BUGIS MRT $2000000 / 506ft² - (ROCHOR, BUGIS MRT) pic real estate - by dealer HDB Scheme Any DBSS BTO

In case you are eligible to purchase landed houses (open solely to Singapore residents) it is without doubt one of the best property investment choices. Landed housing varieties solely a small fraction of available residential property in Singapore, due to shortage of land right here. In the long term it should hold its worth and appreciate as the supply is small. In truth, landed housing costs have risen the most, having doubled within the last eight years or so. However he got here back the following day with two suitcases full of money. Typically we've got to clarify to such folks that there are rules and paperwork in Singapore and you can't just buy a home like that,' she said. For conveyancing matters there shall be a recommendedLondon Regulation agency familiar with Singapore London propertyinvestors to symbolize you

Sales transaction volumes have been expected to hit four,000 units for 2012, close to the mixed EC gross sales volume in 2010 and 2011, in accordance with Savills Singapore. Nevertheless the last quarter was weak. In Q4 2012, sales transactions were 22.8% down q-q to 7,931 units, in line with the URA. The quarterly sales discount was felt throughout the board. When the sale just starts, I am not in a hurry to buy. It's completely different from a private sale open for privileged clients for one day solely. Orchard / Holland (D09-10) House For Sale The Tembusu is a singular large freehold land outdoors the central area. Designed by multiple award-profitable architects Arc Studio Architecture + Urbanism, the event is targeted for launch in mid 2013. Post your Property Condos Close to MRT



  • I had like 17 domains hosted on single account, and never had any special troubles. If you are not happy with the service you will get your money back with in 45 days, that's guaranteed. But the Search Engine utility inside the Hostgator account furnished an instant score for my launched website. Fantastico is unable to install WordPress in a directory which already have any file i.e to install WordPress using Fantastico the destination directory must be empty and it should not have any previous installation files. When you share great information, others will take note. Once your hosting is purchased, you will need to setup your domain name to point to your hosting. Money Back: All accounts of Hostgator come with a 45 day money back guarantee. If you have any queries relating to where by and how to use Hostgator Discount Coupon, you can make contact with us at our site. If you are starting up a website or don't have too much website traffic coming your way, a shared plan is more than enough. Condition you want to take advantage of the worldwide web you prerequisite a HostGator web page, -1 of the most trusted and unfailing web suppliers on the world wide web today. Since, single server is shared by 700 to 800 websites, you cannot expect much speed.



    Hostgator tutorials on how to install Wordpress need not be complicated, especially when you will be dealing with a web hosting service that is friendly for novice webmasters and a blogging platform that is as intuitive as riding a bike. After that you can get Hostgator to host your domain and use the wordpress to do the blogging. Once you start site flipping, trust me you will not be able to stop. I cut my webmaster teeth on Control Panel many years ago, but since had left for other hosting companies with more commercial (cough, cough) interfaces. If you don't like it, you can chalk it up to experience and go on. First, find a good starter template design. When I signed up, I did a search for current "HostGator codes" on the web, which enabled me to receive a one-word entry for a discount. Your posts, comments, and pictures will all be imported into your new WordPress blog.
  • "Convex Hull" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
  1. ↑ 1.0 1.1 Template:Harvtxt, p. 3.
  2. ↑ Template:Harvtxt, p. 6. The idea of partitioning the hull into two chains comes from an efficient variant of Graham scan by Template:Harvtxt.
  3. ↑ Template:Harvtxt, Theorem 3, pages 562–563.
  4. ↑ For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Template:Harvtxt; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196).
  5. ↑ Template:Harvtxt, p. 16.
Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=34461"