On finding rectilinear steiner minimal trees

• Autores: Josep M. Basart i Muñoz , Josep Rifà i Coma
• Localización: Revista de informática y automática, ISSN 0210-8712, Año 22, Nº. 2, 1989, págs. 40-45
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen
  • español

    Se presenta un nuevo algoritmo heurístico que en tiempo polinomial halla una solución al problema del árbol de Steiner usando la métrica rectilínea (Rectilinear Steiner Minimal Tree Problem). El método se basa en la selección de la mejor conexión que se puede establecer entre el conjunto Z de puntos a unir basándose en una ordenación previa de acuerdo con unas coordenadas cartesianas.

    Un caso particular del RSMT que puede ser resuelto más facilmente, se presenta cuando Z se halla en el perímetro Γ de una región convexa R. Se discuten aquí los datos de no existencia de dicha región y se incluye una forma natural de obtener un RSMT para Z a partir de Γ.

  • English

    The following is an explanation of a polynomial-time heuristic algorithm for solving the Rectilinear Steiner Minimal Tree (RSMT) Problem. It is based on the selection of the most appropiate connection of the set Z of given points using a previous sorting of the elements in Z according to their coordinates.

    An easier solvable case for the RSMT appears when the points of Z are on the perimeter Γ of a well-known convex region R. The cases of non-existence of this special Γ -R region are discussed together with a way to obtain a RSMT for Z using Γ.