Usuario: Contraseña:      ¿Olvidó la clave?   registrar

Usuarios revisando este tema :   1 Invitados:





Rectilinear Crossing Number: Nuevo proyecto
Moderador
Registrado:
25/3/2008 0:36
Desde: Pontevedra
Grupo:
Moderadores
Mensajes: 4364
Ausente

Open in new window




Open in new window



About Rectilinear Crossing Number:


Many questions in computational and combinatorial geometry are based on finite sets of points in the Euclidean plane. Several problems from graph theory also fit into this framework, when edges are restricted to be straight. A typical question is the prominent problem of the rectilinear crossing number (related to transport problems and optimization of print layouts for instance): What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains? Here complete graph means that any pair of points is connected by a straight-edge. Moreover we assume general position for the points, i.e., no three points lie on a common line.

It is not hard to see that we can place four points in a way so that no crossing occurs. For five points the drawing shows different ways to place them (these are all different order types (introduced by Goodman and Pollack in 1983)). If you place five points in convex positions then there are five crossings. The best you can do is to get only one crossing (there is no way to draw a complete graph on five points without crossings, even if you allow the edges to be curves). BTW: Maximizing the number of crossings is easy: Just place all n points on a circle to get the maximum of n choose 4 crossings.

For larger point sets it is very hard to determine the best configuration. The main reason is that the number of combinatorially different ways to place those points grows exponentially. For example already for n=11 there are 2,334,512,907 different configurations.

The remarkable hunt for crossing numbers of the complete graph has been initiated by R. Guy in the 1960s. Till the year 2000 only values for n<=9 have been found, in 2001 n=10 was solved and the case n=11 was settled in 2004. The main goal of the current project is to use sophisticated mathematical methods (abstract extension of order types) to determine the rectilinear crossing number for small values of n. So far we have been successful for n <= 17. From very recent (not even published yet) mathematical considerations the rectilinear crossing numbers for n=19 and n=21 are also known. So the most tantalizing problem now is to determine the true value for n=18, which is the main focus of this project.





Sobre Rectilinear Crossing Number:

Muchas preguntas en geometría computacional y combinatoria se basan en conjuntos finitos de puntos en el plano euclidiano. Varios problemas de la teoría de grafos también encajan en este marco, cuando los bordes están restringidos a ser recto. Una pregunta típica es el problema prominente del número cruce rectilíneo (relacionado con los problemas de transporte y la optimización de diseños de impresión, por ejemplo): ¿Cuál es el menor número de pasos de un dibujo de borde recto de la gráfica completa en la parte superior de un conjunto de n puntos en el plano obtiene? Aquí gráfico completo significa que cualquier par de puntos está conectado por un borde recto. Además asumimos la posición general de los puntos, es decir, no hay tres puntos están en una línea común.

No es difícil ver que podemos poner cuatro puntos de una manera para que no cruce se produce. Durante cinco puntos del dibujo muestra diferentes maneras de colocar (estos son todos los tipos de órdenes diferentes (presentado por Goodman y Pollack en 1983)). Si se coloca a cinco puntos en las posiciones convexas entonces hay cinco cruces. Lo mejor que puedes hacer es conseguir un solo paso (no hay manera de dibujar un gráfico completo en cinco puntos sin cruces, incluso si usted permite que los bordes para ser curvas). BTW: Maximizar el número de cruces es fácil: Sólo tiene que colocar todos los n puntos en un círculo para obtener el máximo de n elegir 4 cruces.

Para los más grandes conjuntos de puntos que es muy difícil determinar la mejor configuración. La razón principal es que el número de maneras diferentes combinatoria para colocar los puntos crece exponencialmente. Por ejemplo ya para n = 11 hay 2334512907 configuraciones diferentes.

La caza notable para los números de cruce en la gráfica completa ha sido iniciado por el Sr. R. Guy en la década de 1960. Hasta el año 2000 los únicos valores para n <= 9 se han encontrado, en 2001, n = 10 y se resolvió el caso n = 11 fue colocada en 2004. El objetivo principal del presente proyecto es el uso de sofisticados métodos matemáticos (extensión abstracta de los tipos de órdenes) para determinar el número rectilíneo de paso para valores pequeños de n. Hasta ahora hemos tenido éxito para n <= 17. A partir de consideraciones matemáticas muy recientes (incluso no publicada aún) los números rectilíneas de cruce para n = 19 y n = 21 también son conocidos. Así que el problema más tentadora ahora es determinar el verdadero valor para n = 18, que es el foco principal de este proyecto.





Open in new window


Url proyecto: http://dist.ist.tugraz.at/cape5/

Url equipo:

Server status: http://dist.ist.tugraz.at/cape5/server_status.php

Enviado el: 20/9/2012 19:15
_________________
Open in new window

Open in new window
Transferir el mensaje a otras aplicaciones Transferir a






Puede ver mensajes.
No puede enviar mensajes.
No puede responder mensajes.
No puede editar mensajes.
No puede eliminar mensajes.
No puede crear encuestas.
No puede votar.
No puede adjuntar archivos.
No puede hacer un envío sin aprobación.

[Búsqueda Avanzada]


 

CANAL@Boinc 1997-2008  |  Diseño Rafa Hens sobre idea original de Fran | Reservados todos los derechos