DATOS DEL INVESTIGADOR PRINCIPAL
Nombre	María Isabel David
Nombre del perfíl	Investigador Por Proyecto
Grupo de investigación	Sistemas y Computación
Línea de investigación	Bioinformática e Informática teórica (BIT)
Equipo del proyecto	Diego Arévalo Ovalle Colaborador
TÍTULO DEL PROYECTO	Los Números Reales en Computación Geométrica.
PALABRAS CLAVE	Teoría de la computabilidad; Teoría de Dominios; aritmética real exacta; computación geométrica exacta; Topología de Scott.
OBJETIVOS DEL PROYECTO	Optimizar algunas técnicas en computación geométrica que se han desarrollado con aritmética de punto flotante cambiando el paradigma a computación exacta.
PERTINENCIA ESPISTEMOLÓGICA DEL PROYECTO	Las falencias de representar los números reales por números de punto flotante es notoria en diferentes campos de computación donde se utilizan estructuras de datos continuas. El surgimiento de la computación concreta provee las herramientas necesarias para tratar con datos sobre los números reales y exige el desarrollo de modelos y técnicas alternativas para abordar problemas concretos. Este proyecto pretende brindar elementos a nivel teórico y tecnológico a los investigadores que deseen trabajar en los campos donde las entradas son parciales debido a una aproximación en las entradas de los datos de tipo real y las salidas son altamente sensibles a dichas aproximaciones.
RELEVANCIA DEL PROYECTO PARA LA INSTITUCIÓN Y PARA LOS BENEFICIARIOS DEL PROYECTO	En teoría de computación clásica, las operaciones básicas tales como la suma y la multiplicación, no son operaciones computables. En la topología euclidiana, operaciones fundamentales de geometría tales como la intersección de conjuntos, la función característica que determina el interior y el exterior de un conjunto, son funciones discontinuas. Estos elementos de computabilidad y continuidad deben tenerse en cuenta, de los contrario sería imposible encontrar una solución algorítmica a un problema o, se puede incurrir en resultados erróneos. Para resolver estos inconvenientes, se ha desarrollado la Teoría de la computabilidad concreta, donde la noción de función computable depende de la representación subyacente, y desde luego, se reconsidera la continuidad desde otras estructuras con diferente topología. En este proyecto se trabajará desde la representación de Dominios con la topología de Scott. En computación geométrica surgen problemas cuando se sustituyen los números reales por su aproximación en aritmética de punto flotante. Un ejemplo conocido, es la situación geométrica imposible, causada por cálculos imprecisos y conocida como "las líneas trenzadas de Ramshaw" que debido a la comparación inexacta de coordenadas en y de dos líneas rectas diferentes en coordenadas de x diferentes, con una precisión limitada de aritmética de punto flotante, un programa podría concluir que dos líneas rectas se cruzan más de una vez. Los teoremas de geometría euclidiana sobre los que se sustenta el cálculo gradual de la envolvente convexa de un conjunto también tienen posibles violaciones en el cálculo con aritmética de punto flotante. Es deseable que toda decisión tomada en el programa se tome como si se hubiera hecho con la entrada exacta. Sin embargo, no se exige exactitud numérica, la idea es diseñar algoritmos eficientes que ante entradas con cierta incertidumbre -entradas parciales- tomen decisiones correctas. Para lograr esto, se hace necesaria una representación de los números reales que permita aproximaciones computacionales con cualquier precisión requerida. Tal paradigma se conoce como computación geométrica exacta. La confluencia de campos tales como Análisis Computable, Teoría de Dominios y Computación Exacta son conocimientos que se requiern transferir en el país pues alrededor de ellos hay temas de investigación de punta que poco se trabajan en Latinoamérica a excepción de Buenos Aires.
PROBLEMA DE INVESTIGACIÓN	Diseñar e implementar algoritmos eficientes usando el paradigma de computación geométrica exacta en 2 y 3 dimensiones.
METODOLOGÍA	Causal y descriptiva
RESULTADOS ESPERADOS	Algoritmos eficientes de computación geométrica exacta.
DURACIÓN DEL PROYECTO
POSIBLES FUENTES DE FINANCIACIÓN EXTERNA
REVISIÓN BIBLIOGRÁFICA	Blanck, Jens (2006). Exact real arithmetic using centred intervals and bounded error terms. The Journal of Logic and Algebraic Programming, 66, 50 - 67. Blanck, Jens (2005). Eficient Exact Computation of iterated maps. The Journal of Logic and Algebraic Programming, 64, 41 - 59. Blanck, Jens (1997) Computability on topological spaces by effective domain representations. Ph.D. thesis, Uppsala University. Edalat, Abbas (1997). Domains for computation in mathematics, physics and exact real arithmetic. Bulletin of Symbolic Logic, 3(4), 401-452. Edalat, Abbas & Sünderhauf, Philipp (1997). A domain-theoretic approach to computability on the real line. Edalat, Abbas and Potts, Peter (1998). A new representation for exact real numbers. Electronic Notes in Theoretical Computer Science, 6. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry: Algorithms and Applications (2nd edition). Springer-Verlag, Berlin, Germany. L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap. (2004). Classrom examples of robustness problems in geometric computations. In Proc. ESA 2004. Vasco Brattka, Christiane Frougny and Norbert Mueller (2007). Foreword. RAIRO - Theoretical Informatics and Applications, 41, pp 1-2. Abramsky, Samson & Jung, Achim (1994). Domain theory Handbook of Logic in Computer Science. Clarendo Press. Klaus Weihrauch (1995). Computable Analysis: An Introduction. Springer. B. A. Davey & H. A. Priestley (2002). Introduction to Lattices and Order. Cambridge Press, Second edition. W. Gosper. (1972). Continued fraction arithmetic. Technical Report HACKMEM Item 101,B MIT Artifical Intelligence Memo 239. R. Heckmann, (1999). How Many Arguments Digits Are Needed to produce n Result Digits?, Electronic Notes in Theoretical Computer Science. V. Stoltenberg-Hansen and J. V. Tucker, (2008). Computability on topological spaces via domain representations, New Computational Paradigms Changing Conceptions of What is Computable, Springer, pg. 153-194. V. Stoltenberg-Hansen, I. Lindstrom and E. R. Griffor (1994). Mathematical Theory of Domains, Cambridge University Press.
ENTREGABLES	Un artículo de revisión sobre aritmética real exacta e implementación de operaciones exactas con números reales. Dos artículos de divulgación: Teoría de Dominios para Geometría Computacional, Modelación de sólidos y algoritmos geométricos con números reales exactos. Implementación de algoritmos geométricos eficientes con entradas números reales exactos o datos imprecisos. Un blog en línea a modo de bitácora del proyecto de investigación.
CRONOGRAMA	TIPO DESCRIPCIÓN F.INICIO F.FINAL Entregable Articulo Aritmética Real Exacta 15/01/2013 15/04/2013 Entregable Artículo Teoría de Dominios para Geometría Computacional. 15/03/2013 15/07/2013 Entregable Artículo Modelación de sólidos y algoritmos geométricos con números reales exactos. 15/06/2013 15/12/2013 Entregable Implementación de algoritmos geométricos eficientes con entradas números reales exactos o datos imprecisos. 15/06/2013 15/12/2013 Actividad blog en línea a modo de bitácora del proyecto de investigación. 15/04/2013 15/12/2013
PEDIDO DE BIBLIOGRAFÍA	AUTOR TÍTULO EDITORIAL V. Stoltenberg-Hansen, I. Lindstrom and E. R. Griffor Mathematical Theory of Domains Cambridge University Press Klaus Weihrauch Computability and Complexity in Analysis Springer, Berlin, 2000 Ker-I Ko Complexity Theory of Real Functions Birkhäuser, Boston, 1991 Marian Pour-El and J. Ian Richards Computability in Analysis and Physics Springer, Berlin 1989
ANEXOS