Bounding sphere

Bounding sphere

In mathematics, given a non-empty set of objects of finite extension in n-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an n-dimensional solid sphere containing all of these objects.

In the plane the terms bounding or enclosing circle are used.

Used in computer graphics and computational geometry, a bounding sphere is a special type of bounding volume. There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications. [1]

In statistics and operations research, the objects are typically points, and generally the sphere of interest is the minimal bounding sphere, that is, the sphere with minimal radius among all bounding spheres. It may be proven that such sphere is unique: If there are two of them, then the objects in question lies within their intersection. But an intersection of two non-coinciding spheres of equal radius is contained in a sphere of smaller radius.

The problem of computing the center of a minimal bounding sphere is also known as the "unweighted Euclidean 1-center problem".

Contents

Applications

Clustering

Such spheres are useful in clustering, where groups of similar data points are classified together.

In statistical analysis the scattering of data points within a sphere may be attributed to measurement error or natural (usually thermal) processes, in which case the cluster represents a perturbation of an ideal point. In some circumstances this ideal point may be used as a substitute for the points in the cluster, advantageous in reducing calculation time.

In operations research the clustering of values to an ideal point may also be used to reduce the number of inputs in order to obtain approximate values for NP-hard problems in a reasonable time. The point chosen is not usually the center of the sphere, as this can be biased by outliers, but instead some form of average location such as a least squares point is computed to represent the cluster.

Software for computing the minimal bounding sphere

References

  1. ^ Fast and Tight Fitting Bounding Spheres

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Sphere englobante — Sphère englobante La technique de la Bounding Sphere ou sphère englobante est un algorithme utilisé dans le calcul 3D. Il permet d optimiser la projection d un point sur une surface en 3D. En effet, au lieu de parcourir tous les points de la… …   Wikipédia en Français

  • Bounding volume — A three dimensional model with its bounding box drawn in dashed lines. For building code compliance, see Bounding. In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains …   Wikipedia

  • Sphère englobante — La technique de la Bounding Sphere ou sphère englobante est un algorithme utilisé dans le calcul 3D. Il permet d optimiser la projection d un point sur une surface en 3D. En effet, au lieu de parcourir tous les points de la surface et chercher le …   Wikipédia en Français

  • Sphère cornue d'Alexander — En mathématiques, et plus précisément en topologie, la sphère cornue d Alexander est un célèbre exemple de surface pathologique ; elle fut découverte en 1923 par J. W. Alexander. Sommaire …   Wikipédia en Français

  • sphere — I. noun Etymology: Middle English spere globe, celestial sphere, from Anglo French espere, from Latin sphaera, from Greek sphaira, literally, ball; perhaps akin to Greek spairein to quiver more at spurn Date: 14th century 1. a. (1) the apparent… …   New Collegiate Dictionary

  • Minimum bounding box — The minimum or smallest bounding or enclosing box for a point set in N dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used, the… …   Wikipedia

  • Minimum bounding circle — may refer to: Bounding sphere Smallest circle problem This disambiguation page lists articles associated with the same title. If an internal link led you here, you may wish to change …   Wikipedia

  • Alexander horned sphere — The Alexander horned sphere is one of the most famous pathological examples in mathematics discovered in 1924 by J. W. Alexander. It is the particular embedding of a sphere in 3 dimensional Euclidean space obtained by the following construction,… …   Wikipedia

  • Collision detection — For collision detection on networks see CSMA/CD Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other …   Wikipedia

  • Ограничивающая сфера — (англ. bounding sphere, enclosing sphere, enclosing ball) термин в компьютерной графике и вычислительной геометрии, один из типов ограничивающего объёма (англ. bounding volume). Ограничивающая сфера описывает ограниченную область… …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”