Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Объектілер жиынтығын қамтитын сфера, жазықтық мәселесі
Sphere that contains a set of objects
the planar problem
Математикада, өлшемдік кеңістікте шекті кеңейтуі бар бос емес объектілер жиынтығы берілгенде, мысалы, нүктелер жиынтығы, осы жиынтықты шектейтін сфера, қоршау сферасы немесе қоршау шар – бұл жиынтықтағы барлық объектілерді қамтитын өлшемді қатты сфера болып табылады. Компьютерлік графикада және есептеу геометриясында қолданылатын шектейтін сфера – шектейтін көлемнің ерекше түрі. Нақты уақыт компьютерлік графика қолданбаларында жоғары практикалық құндылығы бар бірнеше жылдам және қарапайым шектейтін сфера құрылыс алгоритмдері бар. Статистикада және операциялар зерттеуінде объектілер әдетте нүктелер болып табылады, ал көбінесе қызығушылық тудыратын сфера – ең кішкентай шектейтін сфера, яғни барлық шектейтін сфералардың арасындағы ең кішкентай радиусы бар сфера. Мұндай сфераның бірегей екендігі дәлелденуі мүмкін: егер олардың екеуі болса, онда сөз болатын объектілер олардың қиылысында орналасады. Бірақ радиусы бірдей екі сфераның қиылысы кішкентай радиусты сфераның ішінде орналасады. Ең кішкентай шектейтін сфераның ортасын есептеу мәселесі "салмақталмаған Евклидтік 1-орталық мәселесі" деп те аталады.
In mathematics, given a non empty set of objects of finite extension in dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is a dimensional solid sphere containing all of these objects. 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. 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 a sphere is unique: If there are two of them, then the objects in question lie 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".
Кластерлеу
Мұндай сфералар кластерлеуде пайдалы, онда ұқсас деректер нүктелерінің топтары бірге жіктеледі. Статистикалық талдауда сфера ішіндегі дерек нүктелерінің таралуы өлшеу қатесіне немесе табиғи (әдетте жылулық) процестерге байланысты болуы мүмкін, мұндай жағдайда кластер идеалды нүктенің бұзылуын көрсетеді. Кейбір жағдайларда бұл идеалды нүкте кластердегі нүктелердің орнына қолданылуы мүмкін, бұл есептеу уақытын қысқартуға ыңғайлы. Операциялық зерттеулерде NP-толық мәселелер үшін жуықтап алғандағы мәндерді ақылға қонымды уақытта алу үшін мәндерді идеалды нүктеге топтастыру арқылы кіріс деректердің санын азайту да қолданылады. Таңдалған нүкте әдетте сфераның ортасы емес, себебі ол сыртқы мәндерге (аутлиерлерге) тәуелді болуы мүмкін, бірақ кластерді бейнелеу үшін ең кішкентай квадраттар әдісімен есептелген орташа орналасқан нүкте сияқты нәрсе қолданылады.
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.
Алгоритмдер
Шектеулі шар мәселесін шешу үшін нақты және жуық алгоритмдер бар.
There are exact and approximate algorithms for the solving bounding sphere problem.
Сызықтық бағдарламалау
Нимрод Мегиддо 1 орталық проблеманы жан-жақты зерттеді және 1980 жылдары кем дегенде бес рет жариялады. 1983 жылы ол "тартып қысқару және іздеу" алгоритмін ұсынды, ол оптималды шектеу сферасын табады және өлшем тұрақты сан ретінде белгіленген жағдайда сызықтық уақытта жұмыс істейді. Егер өлшем ескерілсе, орындалу уақытының күрделілігі , бұл жоғары өлшемді қолданбалар үшін тиімсіз. 1991 жылы Эмо Велцль Реймунд Сейдельдің кездейсоқ сызықтық бағдарламалау алгоритмін кеңейте отырып, әлдеқайда қарапайым кездейсоқ алгоритм ұсынды. Велцль алгоритмінің күтілетін жұмыс уақыты , ал кез келген белгіленген өлшем үшін ол қайтадан азаяды. Мақалада жоғары өлшемдерде оның тиімділігін көрсететін тәжірибелік нәтижелер келтірілген. Тимоти Чанның соңғы детерминистік алгоритмі де уақыт ішінде жұмыс істейді, өлшемге тәуелділігі кішкентай (бірақ әлі де экспоненциалды). Ашық кодты Computational Geometry Algorithms Library (CGAL) Велцль алгоритмінің іске асырылуын қамтиды.
Nimrod Megiddo studied the 1 center problem extensively and published on it at least five times in the 1980s. In 1983, he proposed a "prune and search" algorithm which finds the optimum bounding sphere and runs in linear time if the dimension is fixed as a constant. When the dimension is taken into account, the execution time complexity is , which is impractical for high dimensional applications. In 1991, Emo Welzl proposed a much simpler randomized algorithm, generalizing a randomized linear programming algorithm by Raimund Seidel. The expected running time of Welzl's algorithm is , which again reduces to for any fixed dimension The paper provides experimental results demonstrating its practicality in higher dimensions. A more recent deterministic algorithm of Timothy Chan also runs in time, with a smaller (but still exponential) dependence on the dimension. The open source Computational Geometry Algorithms Library (CGAL) contains an implementation of Welzl's algorithm.
Негізгі жиынтыққа негізделген шамалау
Бадоиу және басқалар шектейтін сфера мәселесіне жуықтауды ұсынды, онда жуықтау дегеніміз – құрастырылған сфераның радиусы ең көп дегенде , мұндағы – шектейтін сфераның мүмкін болатын ең кіші радиусы. Корсет – бұл кішігірім ішкі жиын, оның үстінде бұл ішкі жиынға қолданған шешімнің кеңеюі бүкіл жиын үшін шектейтін сфера болады. Корсет әрбір итерацияда жиынға ең алыс нүктені қосу арқылы кезең-кезеңмен құрылады. Кумар және басқалар бұл жуықтау алгоритмін уақыт ішінде жұмыс істеуі үшін жетілдірді.
Bădoiu et al. presented a approximation to the bounding sphere problem, where a approximation means that the constructed sphere has radius at most , where is the smallest possible radius of a bounding sphere. A coreset is a small subset, that a expansion of the solution on the subset is a bounding sphere of the whole set. The coreset is constructed incrementally by adding the farthest point into the set in each iteration. Kumar et al. improved this approximation algorithm so that it runs in time .
Фишердің нақты шешушісі
Фишер және тағы басқалар (2003) ең нашар жағдайда полиномиалдық есептеу уақыты болмаса да, нақты шешуші алгоритм ұсынды. Алгоритм толығымен комбинаторлық болып табылады және сызықтық бағдарламалаудағы симплекс әдісіне ұқсас айналдыру схемасын іске асырады, бұл схема бұрынғы эвристикаларда қолданылған. Алгоритм барлық нүктелерді қамтитын үлкен шардан басталады және оны одан әрі қысқарту мүмкін болмайынша біртіндеп қысқартады. Алгоритмде бұрынғы авторлар назардан тыс қалдырған дегенерация жағдайларында дұрыс тоқтау шарттары қарастырылған; сондай-ақ, ішінара шешімдерді тиімді өңдеу арқасында айтарлықтай жылдамдыққа қол жеткізіледі. Авторлар алгоритмнің төмен және орташа төмен (10 000-ға дейін) өлшемдерде тиімді екенін растады және оның қозғалатын нүктелік операцияларында сандық тұрақтылық мәселелері жоқ екенін мәлімдеді. Алгоритмнің C++ нұсқасы ашық кодты жоба ретінде қолжетімді.
Fischer et al. (2003) proposed an exact solver, though the algorithm does not have a polynomial running time in the worst case. The algorithm is purely combinatorial and implements a pivoting scheme similar to the simplex method for linear programming, used earlier in some heuristics. It starts with a large sphere that covers all points and gradually shrinks it until it cannot be shrunk further. The algorithm features correct termination rules in cases of degeneracies, overlooked by prior authors; and efficient handling of partial solutions, which produces a major speed up. The authors verified that the algorithm is efficient in practice in low and moderately low (up to 10,000) dimensions and claim it does not exhibit numerical stability problems in its floating point operations. A C++ implementation of the algorithm is available as an open source project.
Төтенше нүктелер оптималдық сфера
шектейтін сфера проблемасын шешу үшін "шектен тыс нүктелердің оңтайлы сферасы" әдісін, жылдамдық пен дәлдікті бақылау арқылы жақындастыру ұсынды. Бұл әдіс бағыт векторлары жиынтығын алып, барлық нүктелерді әрбір векторға проекциялау арқылы жұмыс істейді; жылдамдық пен дәлдік арасындағы айырбас құралы ретінде қызмет етеді. Бұл проекциялардың шектен тыс нүктелеріне нақты шешім табушы қолданылады. Алгоритм қалған нүктелерді қарастырып, қажет болған жағдайда сфераны кеңейтеді. мәні үлкен болғанда, бұл әдіс нақты әдістерге қарағанда бірнеше есе жылдам, сонымен қатар салыстырмалы нәтижелер береді. Ең нашар жағдайдағы уақыты .
proposed the "extremal points optimal sphere" method with controllable speed to accuracy approximation to solve the bounding sphere problem. This method works by taking a set of direction vectors and projecting all points onto each vector in ; serves as a speed accuracy trade off variable. An exact solver is applied to the extremal points of these projections. The algorithm then iterates over the remaining points, if any, growing the sphere if necessary. For large this method is orders of magnitude faster than exact methods, while giving comparable results. It has a worst case time of .