Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет




ИмеТриизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет
Дата на преобразуване09.10.2012
Размер196.58 Kb.
ТипАнализ
източникhttp://vihrushka-topology.googlecode.com/files/Alpha Shapes part 1.doc
Триизмерни Алфа Форми


Herbert Edelsbrunner и Ernst P. Mücke

Илинойски университет


Много често, данните в научните изследвания са в своята абстрактна форма крайно точково множество в пространството (finite point set in space) и понякога е нужно или задължително да се изчисли т.нар. “форма” на множеството. За тази цел с тази статия въвеждаме формално понятието фамилия от -форми в крайно точково множество в 3. Всяка форма е добре дефиниран многостен (well defined polytope) , произхождащ от триангулацията на Delaunay (Delaunay triangulation) на точково пространство, с параметър α  R контролиращ желаното ниво на детайлност. Представен е алгоритъм, който конструира цялата фамилия от форми за едно дадено множество с размерност n със сложност O(n2), в най-лошия случай. Разгледано е издръжливо изпълнение на алгоритъма и няколко приложения в областта на научното изчисляване.


Категории и описание на темата:

F.2.2.[Анализ на алгоритъма и сложност на задачата]: Нечислени алгоритми и задачи;

G.4. [Математика на изчисляването]: Математически софтуер – надеждност и яснота;

I.2.10. [Изкуствен интелект]: Визия и разбиране на случая – представяне, структуриране на данните и преобразувания; форма;

I.3.4. [Компютърна графика]: Графични помощни програми – пакети приложения, графични пакети;

I.3.5. [Компютърна графика]: Изчислителна геометрия и Обекно моделиране – представяне на криви, повърхнини, триизмерни фигури и обекти;

J.2. [Компютърни приложения]: В науките, изучаващи неживата материя (неорганична химия, физика, астрономия и пр.) и инженерните науки.


Основни термини: Алгоритми, надеждност


Допълнителни ключови думи и фрази: Изчислителни графики, триангулация на Delaunay, геометрични алгоритми, точкови пространства, многостени, издръжливи изпълнения, научно изчисляване, научна визуализация, симплициални комплекси, симулирани смущения, триизмерно пространство


1. Въведение

Геометричното понятие на “форма” няма сродно официално значение. С това силно се различава от другите геометрични понятия като диаметър, обем, изпъкнала обвивка (convex hull) и др. Целта на тази статия е да предложи конкретна и официална дефиниция на формата, която може да бъде изчислена и приложена. Не се преполага, че можем да покрием целия обхват от значения, които терминът “форма” има в съвременния език, било то и ограничено само до геометричен контекст. Въпреки това, терминът е достатъчно приспособим, за да съдейства на широк обхват от приложения, включително изучаването на молекулярни структури и разположението на галактиките в нашата вселена (виж Раздел 7).

По-специфично, темата на тази статия е дефинирането и изчислението на формата на крайно точково пространство в триизмерното Евклидово пространство 3. Интуитивно, ние си мислим за пространството като за облак от точки и говорим за формата на облака. Особен аспект на обичайното използване на думата “форма” е това, че неговото значение варира в зависимост от нуждата от детайлност. Тази гледна точка ще бъде отразена чрез дефиниране на фамилии от форми с един параметър простиращи се от “фини” и “локални” до “груби” и “глобални”.

Има задоволително количество от разработки по точковите пространства в 2 и няколко по точковите пространства в 3. Jarvis [1977] е един от първите, които са разгледали проблема с изчисление на формата като генерализация на изпъкналата обвивка на равнинно точково множество. Математически строгата дефиниция за форма е представена по-късно от Edelsbrunner [1983]. Тяхното понятие за -форми е двуизмерния аналог на пространственото понятие, описано в тази статия. Двуизмерните -форми са свързани с точковите модели на Fairfield [1979; 1983] и кръговите диаграми, използвани в двувариантния cluster анализ (bivariate cluster analysis) (виж примера на Moss[1967]. Други графични структури, която има същите функции, са графите на Gabriel [Matula и Sokal 1980], относителния околностен граф (relative-neighbourhood graph) [Toussaint 1980] и тяхната параметризирана версия – β-скелета [Kirkpatrick и Radke 1985].

За 3 Boissonnat [1984] предлага използването на триангулации на Delaunay във връзка с насочването към “изграждане” на едносвързана форма на точково пространство. Нашата концепция за форма е по-основна и математически добре дефинирано. Наскоро, Veltkamp [1992] също генерализира гореспоменатите двуизмерни структури графи, наречени γ-графи. Накрая, забележете бледото подобие между -формите и isosurfaces в 3. Последното е популярна концепция в обемната визуализация (виж за пример Drebin et al.[1988] и Lorenson и Cline [1987]).

Основните части на тази статия са както следва. Официална дефиниция на -форми заедно с илюстриране е представено в Раздел 2. Геометрична концепция свързана с -формите се обсъжда в Раздел 3. Това са -обвивки, -диаграми (също известни като изпълващи пространството диаграми), -комплекси, триангулации на Delaunay и диаграми на Voronoi. Комбинаторен анализ на -формите се предлага в Раздел 4. Чрез използване на триангулации на Delaunay е сравнително лесно да се изчисляват -форми в 3. Алгоритъмът, които се получават са скицирани в Раздел 5. При дадени n точки в 3 той изгражда удобно пълно представяне на фамилия на всички -форми за време О(n2) в най-лошия случай. Този алгоритъм е прилаган от втория автор на тази статия. В Раздел 6 описваме основните аспекти на изпълнението, като неговите структури от данни, как се постига здравината на изпълнението и какво е неговото поведение на практика. Раздел 7 обсъжда някои проблеми на приложенията, които биха имали полза от -формите. Най-накрая, Раздел 8 разглежда вероятно допълнения на вече представените в статията материали.


2. Алфа форми в пространството

Този раздел ни дава интуитивно описание, както и официална дефиниция на тримерните -форми. И двете са подкрепени с илюстрации, които показват множества от точки с примери на членове от техните фамилии от -форми. Надяваме се, че красотата и елегантността на концепцията на -формите, ще бъдат явни след Раздел 3, където се разкрива връзката с други концепции на естествени геометрии.

Интуитивно описание. Концептуално, -формите са генерализация на изпъкналата обвивка на точковите пространства. Нека S е крайно точково пространство в 3, а  - реално число, като 0    . -формa на S е многостен, който не е нито задължително изпъкнал, нито задължително свързан. За  = , -формата е идентична на изпъкналата обвивка на S. Въпреки това, с намалянето на стойността на , -формата се свива постепенно, развивайки кухини. Тези кухини могат да се свързват и да формират обръчи (tunnels), а е възможно даже да се появят дупки (виж Фигура 1).

Интуитивно, част от многостена изчезва когато  стане достатъчно малко, такова че сфера с радиус , или няколко такива сфери да могат да обхванат неговото пространство, без да обхващат точките на S. Гледаме на 3 като на изпълнено със стиропор и точките на S, изградени от по-плътен материал, като скала. Сега си представете сферична гума с радиус . Тя е въздесъща, в смисъл че пробива във всяка една позиция, която обхваща която и да е от разпръснати скали (sprinkled rocks), тоест точките на S. Полученият обект ще наричаме -обвивка (виж Раздел 3). За да ни бъде по-удобно, изправяме повърхнината на обекта, като заменяме правите ръбове с кръгообразни (circular) и триъгълни за сферичните caps. Получения обект е -формата на S (виж Фигура 2). Тя е многостен в сравнително основния си смисъл: може да бъде вдлъбнат и дори несвързан; може да съдържа двумерни триъгълни парчета и едномерни „струни” от ръбове (strings of edges); неговите компоненти могат да бъдат дори малки колкото една точка. Параметърът  контролира максималната „кривина” на всяка кухина на многостена.

Основно състояние. В рамките на тази статия ние взимаме точките на S в тяхната основна форма. Засега, това означава, че никои 4 точки не лежат на една равнина; никои 5 точки не лежат на една сфера; и за всяко фиксирано  най-малката сфера, минаваща през 2, 3 или 4 точки на S има радиус, различен от . По-късно ще разчирим предположението за основното състояние до удобна за нас форма (виж Раздел 5.3). То опростява предстоящите дефиниции, дискусии и алгоротми и се обяснява с програмистка техника, позната като SoS [Edelsbrunner и Mücke 1990]. Този метод симулира безкрайно малко смущение на точките на нивото на геометричен твърдения (predicates) и освобождава програмиста от иначе необходимия case-анализ (виж Раздел 6.2).

Официална дефиниция. За 0 <  < , нека -кълбо (-ball) е отвборено кълб с радиус . За пълнота, 0-кълбо е точка, а -кълбо е отворено полупространство. Едно -кълбо е празно, ако b  S = . Което и да е подмножество Т S, с размерност |T| = k + 1, където 0  k  , определя k-симплекс Т, които е изпъкналата обвивка, кочто е означена също като conv(T). Предположението за основното състояние гарантира, че всички k-симплекси са точно k-мерни. За 0  k  , се твърди, че k-симплексът Т е -exposed, ако съществува празно -кълбо b, с T = b  S , където b е сфера или обикновено ограничение. По този начин, фиксирано , определя множества Fk, от -exposed k-симплекси за 0  k  . -формата на S, означена с I, е многостен, чиито граници се състоят от триъгълниците в F2,, ръбовете на F1, и върхове на F0, (виж Фигура 1 и 2). k-симплексите на Fk,се наричат още k-faces на I.

Все още имаме нужда да уточним кои елементи на 3 – I са вътрешни и кои външни за I. Фиксирайте стойността на  и ще забележите, че всеки -exposed триъгълник T имаме две (не задължително празни) -кълба, b1  b2, такива че T b1 и T b2. Ако и двете –кълба са празни, то на принадлежи на на границата на външните на I. В противен случай, приемаме че b1 е празно, а b2 - не е. В този случай, T огражда вътрешността на I. И по-специално, вътрешността на I и центъра на b1 лежат на различни страни на T. Определението за вътрешна и външна страна на I е вероятно по-естествена в смисъла на триангулациите на Delaunay и комплексите, както са описани в Раздел 3.


3. Свързани геометрични концепции

Има доста малко естествени геометрични концепции, които да са тясно свързани с -формите. Някои от тях се обсъждат в този раздел. Във всеки от случаите ударението е върху това как концепцията е свързана с -формите и как тази връзка може да обогати познанието за -формите. В раздел 3.1 се дискутират -обвивки и -диаграми. Раздел 3.2 кратко представя триангулациите на Delaunay и техните двойнствени въплъщения, известни като диаграми на Voronoi. Приложението на триангулациите на Delaunay на множество точки е в това, че всяка -форма на множеството е underlying пространство на подкомплекс (subcomplex) на триангулацията. Тези подкомплекси са наречени -комплекси и се дефинират в раздел 3.3. Разширения на тези понятия са споменати в раздел 3.4


3.1 Алфа обвивки и алфа диаграми

Припомнете си от раздел 2, че за положително реално , -кълбо се дефинира като отворено кълбо с радиус . За  = 0 това е точка, а за  = , това е отворено полупространство. При дадено крайно множество точки S  3, едно -кълбо е празно, ако b  S = . При 0     , -обвивката на S, означавана с H, се дефинира като допълнението на обединението на всички празни -кълба. Това е формалното съответствие на стиропорния обекта, описан в раздел 2. Примерни членове на фамилията -обвивки са изпъкналата обвивка на S, за  =  и самото S за достатъчно малко . Забележете че H1  H2 ако 1  2.

Друга интересна концепция, дефинирана с -кълба е т.нар. -диаграма на S, означавана с U. За 0 <  < , U е обединението на всички -кълба чиито центрове са точки в S. Забележете, че точка x  3 принадлежи на U тогава и само тогава, когато -кълбото с център x не е празно. Да означим това -кълбо с bx. Това води до следните връзки между H и U.

x  U  bx  H   и

x  H  bx  U

Разглеждаме границата на U. Тя се състои от сферични caps, кръгови арки (circular arcs) и върхове (vertices), които наричаме ъгли. Това са 2-, 1- и 0-faces на U. Тези caps, арки и ъгли са в близко съответствие с върховете, ръбовете и триъгълниците на I. Необходими са няколко дефиниции за да се опишат тези съответствия.

Нека  е фиксирано, като 0 <  <  и нека T е подмножество на S с мощност |T|= k + 1, където 0  k  2. Дефинираме KT =  pTbp, където bp е -кълбото с център p, както преди. Да поредположим, че KT  . За |T| = 1 KT е сфера, зa |T|= 2 KT е кръг, за |T| = 3 KT е двойка точки. От дефиницията следва че KT e -exposed тогава и само тогава, когато KT съдържа поне едно face на границата на U. При |T| = 1, този face е cap; ако |T| = 2, той е арка; ако |T| = 3, той е ъгъл. Този факт може да бъде изразен както следва: T е k-face на I , където 0  k  2  KT съдържа поне един (2-k)-face на U.

Още повече, броят и структурата на (2-k)-faces съдържащи се в са отразени от T и начина, по който се съдържа в I. Например, ако |T| = 3, тогава KT съдържа нула, един или два ъгъла на I, Първо, не съдържа нито един ъгъл тогава и само тогава, когато T не е триъгълник на I. Това е споменато по-горе. Второ KT, съдържа един ъгъл тогава и само тогава, когато T ограничава вътрешността на I. Трето, двете точки на KT са ъгли на U, тогава и само тогава, когато двете страни на T покриват външността на I, т.е. T е триъгълник на I, който не ограничава неговата вътрешност. Такъв триъгълник ще бъде наречен singular в раздел 5.2. Аналогично, ако |T| = 2 и T е ръб наI , тогава всеки ъглов интервал между два съседни триъгълника на I който покрива външността съответства на арка на U, съдържаща се в KT. Ако няма съседен триъгълник (в този случай T е singular ръб) тогава целият кръг KT принадлежи на границата на U. Аналогично твърдение може да се направи за |T| = 1, където сферичните caps на KT съответстват на solid ъгли около върха (vertex)T които покриват външността на I.

Всичко това има смисъл на съответствие 1-към-1 между (2-k)-faces на U и k-faces на , вземайки под внимание че последните са интерпретирани с множествености (multiplicities), отразяващи броя на exposed страни, ъглови интервали или solid ъгли. Това 1-към-1 съответствие запазва инцидентностите. Това предполага че U или по-специално границата на U се представя/изобразява от I, или по-специално the faces на I и техните инцидентности.


3.2 Триангулации на Delaunay и диаграми на Voronoi

Крайно множество точки (finite point set) S  3 дефинира специална триангулация, известна като триангулация на Delaunay на S (вж Edelsbrunner и Preparata и Shamon). При дадени точки в общо положение, тази триангулация е уникална и разпада изпъкналата обвивка на S на тетраедри. Триангулацията носи името на руския математик Boris Delaunay, който я въвежда в своите трудове. Както е обяснено по-нататък, триангулация на Delaunay на S е двойнствена (dual) на друг комплекс, дефиниран от S, известен като диаграма на Voronoi. Двата комплекса са свързани по интересен начин с фамилията от всички -форми на S. Връзката между -формите и триангулациите на Delaunay ще бъде от особено значение за тази статия.

Триангулации на Delaunay : за 0  k  3, означаваме Fk множеството от k-симплекси

T =conv(T), T  S и |T| = k + 1, за които съществуват празни отворени сфери b с

b  S = T. Забележете че F0 = S. Триангулация на Delaunay на S, означавана с D, е симплициалният комплекс (simplicial complex), дефиниран от тетраедрите в F3, триъгълниците F2, ръбовете в F1 и върховете в F0. По дефиниция, за всеки симплекс T  D , съществуват стойности на   0, такива че T е -exposed. Обратно, всеки face на I е симплекс от D. Това поражда следната връзка между триангулацията на Delaunay и границата на I:

Fk = Fk, за 0  k  2

Ползата от тази връзка е в изразяването на фамилията от -форми на S имплицитно чрез триангулациите на Delaunay на S. Това ще бъде детайно описано в раздел 5.

Диаграми на Voronoi: За точка P  S, дефинираме V(p) – Voronoi cell на р, като множеството от точки x  3, такива че Евклидовото разстояние (Euclidian distance) между х и р е по-малко или равно на разстоянието между х и всяка друга точка на S. Всяка Voronoi cell е изпъкнал многостен (convex polyhedron), а колекцията от всички Voronoi cells, по една за всяка точка на S, дефинира диаграма на Voronoi за S, означавана с V. Една voronoi cell ще наричаме и 3-cell на V. Всяка 2-cell на V е сечението на две voronoi cells, всяка 1-cell или ръб е сечение на три 3-cells, а всяка 0-cell или връх и сечението на четири 3-cells. Съществува естествено 1-към-1 съответствие между к-симплексите на D и (3 – к)-cells на V. Нека Т е подмножество на S с мощност |T| = к + 1 с 0  k  3 и дефинираме VT =  pT V(p)

T е к-симплекс от D  VT е (3 – к)-cell на V за 0  k  3

Това съответствие запазва (или обръща) инцидентностите, което означава че D и V са всъщност двойнствени помежду си.

Забележете че VT е множеството от всички точки х, за които съществува празно отворено кълбо bx с център х с T  bx  S. Равенството е в сила тогава и само тогава, когато х принадлежи на вътрешността на VT. Следва че е T -exposed тогава и само тогава, когато  принадлежи на този интервал. Ще използваме този факт по-късно, когато дискутираме как да определим дали симплекс на D е -exposed.


3.3. Алфа комплекси

От това че всички faces на I са симплески на D, следва че че вътрешността на I е естествено триангулирана от тетраедрите на D. Тази идея води до концепцията за -комплексите, дефинирани по-нататък. Един (триизмерен) симплексен комплекс е колекция C от затворени к-симплекси, за 0  k  3, която има следните две свойства

(i) Ако T  C тогава T C за всяко Т’  Т. С други думи, с всеки симплекс T, C съдържа също и всички faces на T.

(ii) Ако T, T C тогава или T  T =  или T  T = TТ’ = conv(T  T’). Забележете че от (i) следва че този face е също в C. С други думи, сечението на всеки два симплекса в C е или празно или face и на двата.

Едно подмножество C’ на C е подкомплекс на C ако също е симплексен комплекс.

Всеки к-симплекс T от D дефинира отворено кълбо bT ограничено от най-малката сфера bT която съдържа всичи точки от Т. Нека Т е радиусът на bT. За к = 3, bT е описаната сфера (circumsphere) на T; за к = 2, описаната окръжност (circumcircle) на T е голяма окръжност на bT, и за к = 1, двете точки в Т са диаметрално противоположни върху bT.

Наричаме bT най-малката описана сфера а Т радиуса на T. За 0  k  3 и

0    3 дефинираме Gk, като множеството от к-симплекси T  D, за които bT е празно и Т < . Нещо повече, дефинираме G0, = S за всяко . Множествата Gk, може и да не дефинират симплексен комплекс защото може да се случи така, че G3, съдържа тетраедър, но не всички триъгълници на този тетраедър (tetrahedron) принадлежат на G2,; аналогично за триъгълници и ръбове. Вземайки това под внимание, дефинираме -комплекс на S, означаван с C като симплексния комплекс чийто к-симплекси са или (1) в Gk,, или (2) те ограничават (к+1)-симплекси на C. По дефиниция, C1 е подкомплекс на C2 ако 1  2.


underlying space на C, означавано с | C|, е обединението на всички симплекси на C, или с други думи, частта от 3, покрита от C. От тук, underlying space на C е многостен в смисъла, дефиниран в раздел 2. Всъщност, имаме следното най-важно свойство на C, което даваме без доказателство

За всяко 0    , I = | C|

Това може да се смята за алтернативна дефиниция на -формите. Така по-лесно могат да се определят интервалите на симплексите на D, споменати по-горе в частта за диаграми на Voronoi. Например, нека T е к-симплекс в D. Ако bT е празно, тогава T принадлежи на C тогава и само тогава, когато   (Т, ]


3.4 Разширения

Дефинициите, представени в раздел 2 и 4 могат да бъдат разширени по много начини. До тук се въздържахме да споменаваме тези разширения за да избегнем ненужни усложнения и за да бъдем верни на съществуващите в момента имплементации на концепциите в тази статия. За пълнота, случаите на отрицателни стойности на , точки с тегла и повече измерения ще се обсъдят сега:

Отрицателни стойности на алфа: Това разширение е описано в Edelsbruner за двуизмерния случай. За отрицателно , -комплекси най-естествено се описват като подкомплекси на т.нар. furthest-point триангулации на Delaunay на S. За T  S и |T|= 4 , тетраедърът T принадлежи на тази триангулация тогава и само тогава, когато bT съдържа всички точки на S – T. -формата е отново the underlying space на -комплекса. Тези форми показват много по-скучни геометрични и топологични свойства от формите с положително  и за това не са толкова интересни в практиката.

Точки с тегла: Припомнете си връзката между -форми и -диаграми, описана в раздел 3.1. Интересно е да се разгледат диаграми за различни размери на кълбото и това всъщност се прави в химията и биологията, където space-filling (изпълващи пространството) диаграми обикновено се дефинират като обединения на кълба с произволни и евентуално различни радиуси. За да могат да се представят такива диаграми чрез многостени, подобни на -форми, е необходимо да се въведат -форми с тегло. Те могат да се дефинират чрез подкомплекси на т.нар. regular триангулации. По дадено крайно множество от точки, всяка с реално тегло, the regular триангулация е уникален симплексен комплекс, чието underlying пространство е изпъкналата обвивка на множеството точки. Ако всички тегла са равни, тогава то съвпада с триангулацията на Delaunay на точките.

Повече измерения: Разбираемо е как ще се обобщят всички по-важни концепции в този раздел за крайни множества от точки в d, за произволно d. Това обобщение, заедно с разширение на точките с тегла, е разработено в Edelsbrunner [1992b]. Забележете все пак че имплементационните детайли стават все по-сложни с увеличаването на измеренията, а сложността в най-лошия случай расте експоненциално. Например, ако S е множество от n точки в d, тогава триангулацията на Delaunay може да съдържа до (n (d + 1) / 2) faces. Въпреки че времето за изпълнение на програмата, конструираща -форми ще расте с увеличаване на d, може да има програми, които гарантират имплементации в малко повече от 3 измерения.


4. Комбинаторен анализ

За разлика от -обвивките и -диаграмите, -формите на крайни множества от точки формират дискретна фамилия, въпреки че са дефинирани за всички реални числа , за които 0   . Всъщност, I 1  I 2 тогава и само тогава, когато

Gk,1Gk,2. От тук I 1  I 2 тогава и само тогава, когато има празна отворено кълбо, ограничено от най-малко описано кълбо на ръб, триъгълник или тетраедър от D, чийто радиус е между 1 и 2. Такъв радиус се нарича -праг (-threshold), защото разделя две -форми. Броят на -формите надвишава с 1 броя на -праговете. Следва че 1 плюс общия брой на к-симплексите в D, за 0    е горна граница (upper bound) за броя на различните -форми. Горна граница на броя на симплексите в D може да се намери чрез връзка между триангулациите на Delaunay в 3 и определен изпъкнал многостен в 4.В следващия параграф кратко описваме тази връзка и посочваме Edelsbrunner и Seidel за детайли.

Lifting Map. 3 се идентифицира с x1x2x3-пространство в 4 т.е. подпространството

x4 = 0. Lifting Map е геометрична трансформация която проектира точки p = (1, 2, 3) в 3 успоредно на оста (axis) x4 върху параболоида (paraboloid) на въртенето U: x4 = xi2 в 4. Нека

pU = (1, 2, 3, i2 ) е образът на p, и дефинираме SU = {pU | p  S}. Изпъкналата обвивка на SU, conv(SU) е изпъкнал многостен с n върха в 4. Една facet принадлежи на долната граница на този многостен ако многостенът лежи от страната на положителната x4 ос на хиперравнината (hyperplane), която съдържа стената. В противен случай, facet принадлежи на горната граница на conv(SU). Ако проектираме всички facet от долната граница на conv(SU) успоредно на оста x4 в 3, заедно с техните subfaces, тогава получаваме триангулацията на Delaunay на S

Горни Граници. Според Теоремата за горните граници на изпъкнал многостен, максималният брой на 1-, 2- и 3-faces на изпъкнал многостен с n  5 върха в 4 е

½(n2 – n), n2-3n и ½(n2-3n) съответно (вж. Bronsted и McMullen and Shepard). The lifting map съдържа същите горни граници за |Fk| за 1  k  3. Всъщност, горната граница за |F3| е с 1 по-малка от броя на 3-faces на conv(SU), защото поне една 3-face принадлежи на горната граница на conv(SU). Според Seidel тези граници са точни, въпреки че върховете на conv(SU) са ограничени да лежат в повърхнина от втора степен в 4. Обобщаваме тези резултати за n = |S|.

|F0| = n

|F1|  ½(n2 – n)

|F2|  n2 – 3n

|F3|  ½(n2 – 3n – 2)

Добавайки 1 към сумата на границите за |F1|, |F2| и |F3|, получаваме

S има най-много 2n2 – 5n различни -форми

Тази граница е твърде песимистична по 2 причини. Първо, въпреки че горните граници на симплексите в D са точни, има много по-малко симплекси за повечето множества от точки. Например, ако n-те точки са равномерно разпределени по единичната окръжност, тогава очакваният брой симплекси е само O(n) (вж. Dwyer [1991]). Второ, не всички отсечки и триъгълници в D имат най-малко описано кълбо, което ограничава празно отворено кълбо. Все пак, след като описаното кълбо на всеки тетраедър от D ограничава празно отворено кълбо по дефиниция, броят на различните –форми е винаги дроб на броя симплекси в D.

Свързани:

Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет icon2. качествен и количествен състав
Всеки флакон от 1 ml разтвор съдържа 135 микрограма пегинтерферон алфа-2a*. Микрограмите показват количеството на частта на интерферон...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconЛитература : на
Русия (роден на 15 март 1930 г в гр. Витебск, Белорусия) и на проф. Херберт Крьомер /Herbert Kroemer/ от Калифорнийския университет...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconСмях и приключения в новата 3D анимация „Алфа и Омега
Кейт е Алфа вълк – за нея дисциплината, дълга и отговорностите са всичко. Хъмфри е Омега вълк – приятелите, забавленията и спокойния...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет icon3. алфа куолити (алфа серт) оод

Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconProf Dr Ernst Kausen © 2006, Aktualisierung 2010

Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconУниверситет курсова работа
Анализ на измененията в изследвания показател и пофакторен анализ на факторите които са предизвикали изменения в показателя стокооборот...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет icon"Алфа Рисърч": 14% са за партия на протестиращите
Герб срещу 17,4% за бсп. Това сочат данните от национално представително проучване на “Алфа Рисърч”, проведено на 22-27 март. Спрямо...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconПротокол
Заседанието беше открито на 18 Декември 2007 г., вторник, в 16. 05 ч., под председателството на Herbert Bösch (председател)
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет iconТ ракийски университет стара загора департамент за информация и повишаване квалификацията на учителите
На вашето внимание предлагаме програма от дългосрочни и краткосрочни форми на следдипломна квалификация, които ще се проведат през...
Триизмерни Алфа Форми Herbert Edelsbrunner и Ernst P. Mücke Илинойски университет icon2 Форми на организация на икономическия живот на обществото
Нито едно общество, било то антично или съвременно, не може без форми и системи на икономическа организация. Историята на обществото...
Поставете бутон на вашия сайт:
Документация


Базата данни е защитена от авторски права ©bgconv.com 2012
прилага по отношение на администрацията
Документация
Дом