Минимална тежина триангулације

У рачунарској геометрији и информатици, минимална тежина триангулације је проблем налажења триангулације са најмањом укупном дужином гране . То је, улазни многоугао или конвексни омотач улазног скупа тачака који се мора поделити у троуглове који су спојени ивица са ивицом и теме (чвор) са теменом, на такав начин да смање збир обима труоглова. Проблем је НП тежак пробем за скуп улазних тачака, али се може апроксимирати до било које жељене прецизности. За улазе многоуглова, може се решити тачно у полиномијалномвремену. Минимална тежинска триангулација се такође некад назива као оптимална триангулација.

Историја

Проблем минималне тежине триангулације скупа тачака је поставио Düppe & Gottschalk 1970, који је предложио захтев за конструкцију троугаоне неправилне мреже модела земљишне контуре, и користи похлепни алгоритам за апроксимацију. Shamos & Hoey 1975 је претпоставио да се мимална тежина триангулације увек подудара са Деланеј триангулацијом, али то је брзо оборио Lloyd 1977, и заправо Kirkpatrick 1980 показао да тежине две триангулације се могу разликовати по линеарном фактору.

Проблем минималне тежине триангулације је постао важан када је Garey & Johnson 1979 сврстао овај проблем у листу нерешених проблема који су НП-комплетни проблеми, и многи каснији аутори су касније објавили парцијалне резултате о томе. Коначно, Mulzer & Rote 2008 је показао да је проблем НП тежак проблем, и Remy & Steger 2009 је показао да се тачна апроксимација може ефикасно направити.

Сложеност

Тежина триангулације скупа тачака у дводимензионалном простору је дефинисана као збир дужина тих грана. Проблем одлучивања је проблем где се испитује да ли постоји триангулација са тежином мањом од дате тежине; доказано је да је то НП-тежак проблем а доказао га је Mulzer & Rote 2008. Доказ се састоји из смањења сложености "PLANAR-1-IN-3-SAT", специјалног случаја САТ проблема у коме Конјунктивна нормална форма чији је граф планаран и прихваћен је кад има тачан задатак који задовољава тачно један литерал у сваком услову. Доказ користи сложене уређаје, и захтева рачунарску асистенцију да би се доказало тачна понашање ових уређаја.

Не зна се да ли је минимала тежина триангулације НП комплетан проблем, пошто ово зависи од познатог проблема који се пита да ли се сума радикала може израчунати у полиномијалном времену. Међутим, Мазлер и Роут су напоменули да је проблем НП потпун проблем ако су тежине чворова заокружене на целобројне вредности.

Иако је НП тежак проблем, може се конструисати у подекспоненцијалном времену алгоритмом динамичког програмирања, који разматра све могуће једноставне сепараторске циклусе са $O({\sqrt {n}})$ тачкама у триангулацији, и рекурзивно налази оптималну триангулацију на свакој страни циклуса, и бира сепаратора циклуса према најмањој укупној тежини. Укупно време ове методе је $2^{O({\sqrt {n}}\log n)}$.

Апроксимација

Неколико аутора је доказало резултате поређења минималне тежине триангулације са са осталим триангулацијама у смислу апроксимације односа, најгори случај односа укупне дужине грана алтернативне триангулације према минималној тежини триангулације. Познато је да Делајнова триангулација има апроксимациони однос $\Theta (n)$, и то је похлепна триангулација (триангулација формирана додавањем грана у поретку од најкраће до најдуже, на сваком кораку укључујући грану кадгод не прелази ранију грану) има апроксимациони однос $\Theta ({\sqrt {n}})$. Ипак, за неке насумично испоручене скупове тачака, обе триангулације, и Делајнова и похлепна триангулација, су у логаритамском фактору минималне тежине.

Најтежи резултат Мазлера и Роута такође подразумева НП тешко проналажење приближног решења са релативном апроксимационом грешком са највише O(1/n²). Дакле, потпуна полиномијална апроксимација шеме за минималну тежину триангулацијје је неизвесно. Међутим, квази-полиномијална апроксимација шеме је могућа: за било коју константу ε > 0, решење са апроксимационим односом 1 + ε се може наћи у квази-полиномијалном времену експ (O((log n)⁹).

Хеуристика

Пошто је тешко наћи тачна решења минималне тежинске триангулације, многи аутори су проучавалихеуристику која може у неким слчајевима пронаћи решење иако се не може доказати да оно ради у свим случајевима. У неким случајевима, многа од ових истраживања су се фокусирала на проблем налажења скупова грана који су загарантовани да припадају минималној тежинској триангулацији. Ако је подграф минималне тежинске триангулације повезан, онда преостали нетроугаони простор се може видети као простор за формирање једноставног многоугла, и цела триангулација се може наћи користећи динамичко програмирање како би се нашло оптимална триангулација овог многоугаоног простора. Исти приступ (динамичко програмирање) се може искористити за случај када подграф има ограничен број повезаних компоненти, и исти приступ се може користити за проналажења повезаног графа и примену динамичког програмирања (ДП) да се попуне рупе многоугла (које окружују гране графа), такође се користи као део хеуристике за проналазак мале тежине али не и минималне тежине триангулације.

Граф који настаје повезивањем две тачке кад год су један другом најближи суседи, је подграф минималне тежинске триангулације. Међутум, овај најближи суседни граф је одговарајући, и зато није никад повезан. Везана линија претраге поналази највеће поодграфове минималне тежинске триангулације користећи кружно базирани β-скелете, геометријси граг који настаје укључивањем гране између две тачке u и v када год не постоји трећа тачка w која формира угао uwv који је већи од неког параметра θ. Доказано је да, за довољно мале вредности θ, граф који настај формирањем на овај начин је подграф минималне тежинске триангулације. Међутим, избор θ мора обезбедити да је овај мањи од угла θ = 90ª за који је β-костур увек повезан.

Техника која је више софистицирана се зове "LMT-костур" који је предложио Dickerson & Montague 1996. Формиран је итеративним процесом, у ком два скупа грана се одржавају, скуп грана који припада минималној тежинској триангулацији и скуп грана који су кандидати за припадање. Иницијално, скуп попзнатих грана је иницијализован на конвексни омотач улаза, и сви преостали парови чворова формирају гране. Затим, у свакој итерацији процеса конструкције, гране које су кандидати се бришу кад год не постоји пар троуглова који је формиран од преосталих грана које формирају четвороугао, за који је кандидат грана најкраћа дијагонала, и гране кандидати се померају у скуп познатих грана када не постоји друге кандидат гране која укршта њих. "LMT-костур" је дефинисан да буде скуп познатих грана који се проузводи након што се овај процес заврши без икаквих промена. Загарантовано је да ће бити подграф минималне тежинске триангулације, који се може конструисати ефикасно, и у експериментима са скуповима до 200 тачака. Међутим, доказано је да на просечно великим скуповима тачака има линеаран број повезаних компоненти.

Остале хеуристике које су биле прихваћене проблему минималне тежинске триангулације укључује генетске алгоритме сепарација и евалуација, у мрављи алгоритам.

Варијације

Триангулација многоугла минималне тежине се може конструисати у кубном времену користећи ДП приступ, што је саопштио Gilbert 1979 и Klincsek 1980. У овој методи, чворови су означени бројевима узастопно окок границе многоугла, и за сваки дијагонални чвор i до чвора j који лежи између многоугла, оптимална триангулација се израчунава узимајући у обзир све могуће торуглове ijk у многоуглу, додавањем тежине оптималне триангулације испод дијагонала ik и jk, и бирање чвора k који води до минималне ускупне тежине. То је, ако MWT(i,j) представља тежину минималне тежинске триангулације за многоугао испод гране ij, онда општи алгоритам има следеће кораке:

• За сваку могућу вредност i, од n − 1 све до 1, ради:
  • За сваку могућу вредност j, од i + 1 до n, ради:
    • Ако је ij грана многоугла, скуп MWT(i,j) = length(ij)
    • Ако ij није унутрашња грана многоугла, скуп MWT(i,j) = +∞
    • Иначе скуп MWT(i,j) = length(ij) + min_{i < k < j} MWT(i,k) + MWT(k,j)

После ове завршетка ове итерације, MWT(1,n) ће садржати укупне тежине минималне тежинске триангулације. Триангулације се може добити рекурзивном претрагом кроз низ, почевши од MWT(1,n), а на сваком кораку бира троугао ijk који води до минималне вредности за MWT(i,j) и рекурзивно претражује MWT(i,k) и MWT(j,k).

Слично ДП метода може такође да се примени на улазних скуп тачака где све осим константног броја тачака лежена конвексном омотачу улаза, и на скупу тачака које леже на константном броју угнежђеног конвексног многоугла или на константном броју линија од којих ни једне две се не укрштају у конвексном омотачу.

такође је могуће формулисати верзију скупа тачака или проблема триангулације многоугла, у коме је једној дозвољено да додаје штајнерове тачке, додатне чворове, у таквом поретку да смањи укупну дужину грана резултујуће триангулације. У неким случајевим, резултујућа триангулација може бити краћа од минималне тежинске триангулације за онолико колики је линеарни фактор. Могуће је апроксимирати минималну тежину штајнерове триангулације скупа тачака унутар константног оптималног, али константни фактор у апроксимацији је велики.

Сродни проблем су такође били проучавани укључујући конструкцију минималне тежине псеудотриангулације аи карактеристика графова минималне тежине триангулације.

Референце

• Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Speckmann, Bettina (2009), „On minimum weight pseudo-triangulations”, Computational Geometry Theory and Applications, 42 (6-7): 627—631, MR 2519380, doi:10.1016/j.comgeo.2008.10.002 .
• Aichholzer, Oswin; Aurenhammer, Franz; Hainz, Reinhard (1999), „New results on MWT subgraphs”, Information Processing Letters, 69 (5): 215—219, doi:10.1016/S0020-0190(99)00018-6 .
• Anagnostou, Efthymios; Corneil, Derek (1993), „Polynomial-time instances of the minimum weight triangulation problem”, Computational Geometry. Theory and Applications, 3 (5): 247—259, MR 1251594, doi:10.1016/0925-7721(93)90016-Y .
• Beirouti, Ronald; Snoeyink, Jack (1998), „Implementations of the LMT heuristic for minimum weight triangulation”, Proc. 14th ACM Symposium on Computational Geometry, стр. 96—105, doi:10.1145/276884.276895 .
• Bose, Prosenjit; Devroye, Luc; Evans, William (1996), „Diamonds are not a minimum weight triangulation's best friend”, Proc. 8th Canadian Conference on Computational Geometry (CCCG 1996) (PDF), стр. 68—73 .
• Capp, Kerry; Julstrom, Bryant A. (1998), „A weight-coded genetic algorithm for the minimum weight triangulation problem”, Proc. ACM Symposium on Applied Computing, Atlanta, Georgia, United States, стр. 327—331, doi:10.1145/330560.330833 .
• Cheng, Siu-Wing; Golin, Mordecai; Tsang, J. (1995), „Expected case analysis of β-skeletons with applications to the construction of minimum weight triangulations”, Proc. 7th Canadian Conference on Computational Geometry (CCCG 1995), стр. 279—284 .
• Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), „A study of the LMT-skeleton”, Algorithms and Computation, Lecture Notes in Computer Science, 1178, стр. 256—265, doi:10.1007/BFb0009502 .
• Cheng, Siu-Wing; Xu, Yin-Feng (2001), „On β-skeleton as a subgraph of the minimum weight triangulation”, Theoretical Computer Science, 262 (1–2): 459—471, doi:10.1016/S0304-3975(00)00318-2 .
• De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), „3.2.3 Greedy and minimum weight triangulations”, Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, 25, Springer, стр. 102—107, ISBN 978-3-642-12970-4 .
• Dickerson, Matthew T.; Montague, Mark H. (1996), „A (usually?) connected subgraph of the minimum weight triangulation”, Proc. 12th ACM Symposium on Computational Geometry, стр. 204—213, doi:10.1145/237218.237364 .
• Düppe, R. D.; Gottschalk, H. J. (1970), „Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten”, Allgemeine Vermessungs-Nachrichten, 77: 423—426 . As cited by Mulzer & Rote 2008 and Remy & Steger 2009.
• Eppstein, David (1994), „Approximating the minimum weight Steiner triangulation” (PDF), Discrete and Computational Geometry, 11 (2): 163—191, MR 1254088, doi:10.1007/BF02574002 .
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, Calif.: W. H. Freeman, Problem OPEN12. стр. 288, ISBN 978-0-7167-1045-5, MR 519066 .
• Gilbert, P. D. (1979), New results in planar triangulations, Report R-850, Urbana, Illinois: Coordinated Science Laboratory, University of Illinois .
• Grantson, M.; Borgelt, C.; Levcopoulos, C. (2005), „Minimum weight triangulation by cutting out triangles”, Proc. 16th International Symposium on Algorithms and Computation, стр. 984—994 .
• Gudmundsson, Joachim; Levcopoulos, Christos (2007), „Minimum weight pseudo-triangulations”, Computational Geometry Theory and Applications, 38 (3): 139—153, MR 2352529, doi:10.1016/j.comgeo.2007.05.004 .
• Heath, L. S.; Pemmaraju, S. V. (1994), „New results for the minimum weight triangulation problem”, Algorithmica, 12 (6): 533—552, MR 1297812, doi:10.1007/BF01188718 .
• Hoffmann, M.; Okamoto, Y. (2004), „The minimum weight triangulation problem with few inner points”, Proc. 1st International Workshop on Parameterized and Exact Computation, стр. 200—212 .
• Hu, Shiyan (2010), „A new asymmetric inclusion region for minimum weight triangulation”, Journal of Global Optimization, 46 (1): 63—73, MR 2566136, doi:10.1007/s10898-009-9409-z .
• Jahani, M.; Bigham, B.S.; Askari, A. (2010), „An ant colony algorithm for the minimum weight triangulation”, International Conference on Computational Science and Its Applications (ICCSA), стр. 81—85, doi:10.1109/ICCSA.2010.38 .
• Keil, J. Mark (1994), „Computing a subgraph of the minimum weight triangulation” (PDF), Computational Geometry: Theory & Applications, 4 (1): 18—26, doi:10.1016/0925-7721(94)90014-0 .
• Kirkpatrick, David G. (1980), „A note on Delaunay and optimal triangulations”, Information Processing Letters, 10 (3): 127—128, MR 566856, doi:10.1016/0020-0190(80)90062-9 .
• Klincsek, G. T. (1980), „Minimal triangulations of polygonal domains”, Annals of Discrete Mathematics, 9: 121—123, doi:10.1016/s0167-5060(08)70044-x .
• Knauer, Christian; Spillner, Andreas (2006), „A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators”, Graph-theoretic concepts in computer science, Lecture Notes in Computer Science, 4271, Berlin: Springer, стр. 49—57, MR 2290717, doi:10.1007/11917496_5 .
• Kyoda, Yoshiaki; Imai, Keiko; Takeuchi, Fumihiko; Tajima, Akira (1997), „A branch-and-cut approach for minimum weight triangulation”, Algorithms and Computation (Singapore, 1997), Lecture Notes in Computer Science, 1350, Berlin: Springer, стр. 384—393, MR 1651067, doi:10.1007/3-540-63890-3_41 .
• Lenhart, William; Liotta, Giuseppe (2002), „The drawability problem for minimum weight triangulations”, Theoretical Computer Science, 270 (1-2): 261—286, MR 1871072, doi:10.1016/S0304-3975(00)00383-2 .
• Levcopoulos, Christos (1987), „An Ω(√n) lower bound for the nonoptimality of the greedy triangulation”, Information Processing Letters, 25 (4): 247—251, MR 896144, doi:10.1016/0020-0190(87)90170-0 .
• Levcopoulos, Christos (2008), „Minimum Weight Triangulation”, Ур.: Kao, Ming-Yang, Encyclopedia of Algorithms, Springer, стр. 546—548, ISBN 978-0-387-30770-1 .
• Levcopoulos, C.; Krznaric, D. (1998), „Quasi-greedy triangulations approximating the minimum weight triangulation” (PDF), Journal of Algorithms, 27: 303—338, MR 1622398, doi:10.1006/jagm.1997.0918 .
• Lingas, Andrzej (1986), „The Greedy and Delaunay triangulations are not bad in the average case”, Information Processing Letters, 22 (1): 25—31, doi:10.1016/0020-0190(86)90038-4 .
• Lingas, Andrzej (1987), „A new heuristic for minimum weight triangulation”, SIAM Journal on Algebraic and Discrete Methods, 8 (4): 646—658, MR 918066, doi:10.1137/0608053 .
• Lingas, Andrzej (1998), „Subexponential-time algorithms for minimum weight triangulations and related problems”, Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98) .
• Lloyd, E. (1977), „On triangulations of a set of points in the plane”, Proc. 18th IEEE Symposium on Foundations of Computer Science, стр. 228—240 .
• Manacher, Glenn K.; Zobrist, Albert L. (1979), „Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation”, Information Processing Letters, 9 (1): 31—34, MR 537055, doi:10.1016/0020-0190(79)90104-2 .
• Meijer, Henk; Rappaport, David (1992), „Computing the minimum weight triangulation of a set of linearly ordered points”, Information Processing Letters, 42 (1): 35—38, MR 1160443, doi:10.1016/0020-0190(92)90129-J .
• Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2), Article A11, arXiv:cs.CG/0601002 , doi:10.1145/1346330.1346336 .
• Plaisted, D. A.; Hong, J. (1987), „A heuristic triangulation algorithm”, Journal of Algorithms, 8: 405—437, doi:10.1016/0196-6774(87)90020-4 .
• Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), „A genetic algorithm for the minimum weight triangulation”, IEEE International Conference on Evolutionary Computation, стр. 541—546, doi:10.1109/ICEC.1997.592370 .
• Remy, Jan; Steger, Angelika (2009), „A quasi-polynomial time approximation scheme for minimum weight triangulation” (PDF), Journal of the ACM, 56 (3), Article A15, doi:10.1145/1516512.1516517 .
• Shamos, M. I.; Hoey, D. J. (1975), „Closest-point problems”, Proc. 16th IEEE Symposium on Foundations of Computer Science (PDF), стр. 151—162 .
• Wang, Cao An; Yang, Boting (2001), „A lower bound for β-skeleton belonging to minimum weight triangulations”, Computational Geometry: Theory & Applications, 19 (1): 35—46, doi:10.1016/S0925-7721(01)00008-6 .
• Xu, Yin-Feng (1998), „Minimum weight triangulations”, Handbook of Combinatorial Optimization, Vol. 2, Boston, MA: Kluwer Academic Publishers, стр. 617—634, MR 1665412 .
• Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994), „A chain decomposition algorithm for the proof of a property on minimum weight triangulations”, Ур.: Du, Ding-Zhu; Zhang, Xiang-Sun, Algorithms and Computation: 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25–27, 1994, Proceedings, Lecture Notes in Computer Science, 834, Berlin: Springer, стр. 423—427, MR 1316441, doi:10.1007/3-540-58325-4_207 .

Спољашње везе

• Minimum Weight Triangulation using an LMT Skeleton source code'