Davenport–Schinzel Sequences and Their Geometric Applications es un libro de geometría discreta escrito por Micha Sharir y Pankaj K. Agarwal y publicado por Cambridge University Press en 1995, con una reimpresión en rústica en 2010.
Las secuencias de Davenport-Schinzel reciben su nombre de Harold Davenport y Andrzej Schinzel , quienes las aplicaron a ciertos problemas en la teoría de ecuaciones diferenciales . [1] Son secuencias finitas de símbolos de un alfabeto dado , restringidas al prohibir que pares de símbolos aparezcan en alternancia más de un número dado de veces (sin importar qué otros símbolos puedan separarlos). En una secuencia de Davenport-Schinzel de orden , las alternancias más largas permitidas tienen longitud . Por ejemplo, una secuencia de Davenport-Schinzel de orden tres podría tener dos símbolos y que aparezcan en el orden o , pero las alternancias más largas como estarían prohibidas. La longitud de dicha secuencia, para una elección dada de , puede ser solo ligeramente mayor que su número de símbolos distintos. Este fenómeno se ha utilizado para demostrar límites casi lineales correspondientes en varios problemas de geometría discreta , por ejemplo, mostrando que la cara ilimitada de una disposición de segmentos de línea puede tener una complejidad que es solo ligeramente superlineal. El libro trata sobre esta familia de resultados, tanto sobre la limitación de las longitudes de las secuencias de Davenport-Schinzel como sobre sus aplicaciones a la geometría discreta. [2]
Los tres primeros capítulos del libro proporcionan límites a las longitudes de las secuencias de Davenport-Schinzel cuya superlinealidad se describe en términos de la función inversa de Ackermann . Por ejemplo, la longitud de una secuencia de Davenport-Schinzel de orden tres, con símbolos, puede ser como máximo , [3] como muestra el segundo capítulo; el tercero se ocupa de órdenes superiores. El cuarto capítulo aplica esta teoría a segmentos de línea e incluye una prueba de que los límites demostrados utilizando estas herramientas son estrictos: existen sistemas de segmentos de línea cuya complejidad de ordenamiento coincide con los límites de la longitud de la secuencia de Davenport-Schinzel. [1]
Los capítulos restantes tratan de aplicaciones más avanzadas de estos métodos. Tres capítulos tratan de disposiciones de curvas en el plano, algoritmos para disposiciones y disposiciones de dimensiones superiores [1] , después de lo cual el capítulo final (que comprende una gran fracción del libro) trata de aplicaciones de estos límites combinatorios a problemas que incluyen diagramas de Voronoi y búsqueda del vecino más cercano , la construcción de líneas transversales a través de sistemas de objetos, problemas de visibilidad y planificación del movimiento de robots . [4] El tema sigue siendo un área activa de investigación y el libro plantea muchas preguntas abiertas. [1]
Aunque está dirigido principalmente a investigadores, este libro (y especialmente sus primeros capítulos) también podría utilizarse como libro de texto para un curso de posgrado en lo que respecta a su contenido. El crítico Peter Hajnal lo califica de "muy importante para cualquier especialista en geometría computacional" y "muy recomendable para cualquiera que esté interesado en este nuevo tema en la frontera entre la combinatoria, la geometría y la teoría de algoritmos". [1]
