Diferencia entre revisiones de «Triangulación de peso mínimo»

De Wikipedia, la enciclopedia libre
Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Jespa (discusión · contribs.)
2132 ediciones
mSin resumen de edición
Línea 18: Línea 18:


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

==Enlaces externos ==
*[http://code.google.com/p/minimum-weight-triangulator/ Minimum Weight Triangulation using an LMT Skeleton source code]'


[[Categoría:Algoritmos geométricos]]
[[Categoría:Algoritmos geométricos]]

Revisión del 15:51 20 feb 2017

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada.
Busca fuentes: «Triangulación de peso mínimo» – noticias · libros · académico · imágenes
Este aviso fue puesto el 20 de febrero de 2017.
Dos posibles descomposiciones en triángulos del mismo polígono, siendo la izquierda de menor peso que la derecha.

En geometría computacional, se denomina problema de triangulación de peso mínimo al problema de encontrar una triangulación de longitud de borde total mínima.[1]​ Es decir, dado un polígono de entrada (o el cierre convexo de un conjunto de puntos de la entrada) encontrar la subdivisión del mismo en triángulos adyacentes, de tal manera que se minimice la suma de los perímetros de los triángulos. El problema es NP-duro para entradas consistentes en conjuntos de puntos, pero puede ser aproximado con cualquier grado deseado de exactitud. Si la entrada consiste en un polígono, puede ser solucionado exactamente en tiempo polinómico. La triangulación de peso mínimo también se ha denominado a veces la triangulación óptima.

Historia

El problema de triangulación de peso mínimo de un conjunto de puntos fue propuesto por Düppe y Gottschalk (1970) , quienes sugirieron su aplicación a la construcción de redes irregulares de triángulos para representar contornos terrestres , proponiendo un algoritmo voráz para aproximarlo. Shamos y Hoey (1975)  conjeturaron que la triangulación de peso mínimo siempre coincidiría con la triangulación de Delaunay, pero esto fue rápidamente refutado por Lloyd (1977), y de hecho Kirkpatrick (1980) mostró que los pesos de las dos triangulaciones pueden diferir por un factor lineal.[2]​

El problema de triangulación de peso mínimo se hizo notorio cuándo Garey y Johnson (1979) lo incluyeron en una lista de problemas abiertos en su libro sobre completitud NP, y muchos autores posteriores publicaron resultados parciales sobre ello. Finalmente, Mulzer y Rote (2008) demostró que el problema era NP-duro, y Remy y Steger (2009) mostró que es posible construir aproximaciones al mismo de forma eficiente.

Complejidad

El peso de una triangulación de un conjunto de puntos en el plano euclídeo está definido como la suma de longitudes de sus bordes. Su problema de decisión consiste en decidir si existe alguna triangulación de peso inferior a un peso dado. Se demostró que este en un problema NP-duro por Mulzer y Rote (2008), mediante una demostración por reducción de grafo plano 1-EN-3, un caso especial del problema de satisfacibilidad booleana en el que un 3-CNF cuyo grafo es planar es aceptado cuándo satisface la condición un literal en cada cláusula. La demostración empleó ayuda de un ordenador para verificar el comportamiento correctode la misma.

No es sabido si el problema de triangulación de peso mínimo es NP-completo, ya que este depende del problema aún abierto de determinar si la suma de radicales puede ser computada en tiempo polinómico. Aun así, Mulzer y Rote remarcaron que el problema es NP-completo si los pesos de borde son redondeados a valores enteros.

Notas

  1. ↑ For surveys of the problem, see Xu (1998), Levcopoulos (2008), and De Loera, Rambau y Santos (2010).
  2. ↑ See also Manacher y Zobrist (1979).

Referencias

Enlaces externos

Obtenido de «https://es.wikipedia.org/w/index.php?title=Triangulación_de_peso_mínimo&oldid=97039274»