From the Icosahedron to Natural Triangulations of CP(2) and S(2) x S(2)

We present two constructions in this paper: (a) a 10-vertex triangulation CP(10)(2) of the complex projective plane CP(2) as a subcomplex of the join of the standard sphere (S(4)(2)) and the standard real projective plane (RP(6)(2), the decahedron), its automorphism group is A(4); (b) a 12-vertex triangulation (S(2) x S(2))(12) of S(2) x S(2) with automorphism group 2S(5), the Schur double cover of the symmetric group S(5). It is obtained by generalized bistellar moves from a simplicial subdivision of the standard cell structure of S(2) x S(2). Both constructions have surprising and intimate relationships with the icosahedron. It is well known that CP(2) has S(2) x S(2) as a two-fold branched cover; we construct the triangulation CP(10)(2) of CP(2) by presenting a simplicial realization of this covering map S(2) x S(2) -> CP(2). The domain of this simplicial map is a simplicial subdivision of the standard cell structure of S(2) x S(2), different from the triangulation alluded to in (b). This gives a new proof that Kuhnel's CP(9)(2) triangulates CP(2). It is also shown that CP(10)(2) and (S(2) x S(2))(12) induce the standard piecewise linear structure on CP(2) and S(2) x S(2) respectively.

chain complex and quadrilaterals for normal surfaces

We interpret a normal surface in a (singular) three-manifold in terms of the homology of a chain complex. This allows us to study the relation between normal surfaces and their quadrilateral coordinates. Specifically, we give a proof of an (unpublished) observation independently given by Casson and Rubinstein saying that quadrilaterals determine a normal surface up to vertex linking spheres. We also characterize the quadrilateral coordinates that correspond to a normal surface in a (possibly ideal) triangulation.

Hardness results for computing optimal locally Gabriel graphs

Delaunay and Gabriel graphs are widely studied geo-metric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Lo-cally Gabriel Graphs (LGGs) have been proposed. We propose another generalization of LGGs called Gener-alized Locally Gabriel Graphs (GLGGs) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique LGG or GLGG for a given point set because no edge is necessarily in-cluded or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. We show that computing an edge max-imum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with dilation ≤k is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph G= (V, E) is a valid LGG.

Non-existence of tight neighborly triangulated manifolds with beta(1)=2

All triangulated d-manifolds satisfy the inequality ((f0-d-1)(2)) >= ((d+2)(2))beta(1) for d >= 3. A triangulated d-manifold is called tight neighborly if it attains equality in this bound. For each d >= 3, a (2d + 3)-vertex tight neighborly triangulation of the Sd-1-bundle over S-1 with beta(1) = 1 was constructed by Kuhnel in 1986. In this paper, it is shown that there does not exist a tight neighborly triangulated manifold with beta(1) = 2. In other words, there is no tight neighborly triangulation of (Sd-1 x S-1)(#2) or (Sd-1 (sic) S-1)(#2) for d >= 3. A short proof of the uniqueness of K hnel's complexes for d >= 4 under the assumption beta(1) not equal 0 is also presented.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.

Simple crystallizations of 4-manifolds

Minimal crystallizations of simply connected PL 4-manifolds are very natural objects. Many of their topological features are reflected in their combinatorial structure which, in addition, is preserved under the connected sum operation. We present a minimal crystallization of the standard PL K3 surface. In combination with known results this yields minimal crystallizations of all simply connected PL 4-manifolds of ``standard'' type, that is, all connected sums of CP2, S-2 x S-2, and the K3 surface. In particular, we obtain minimal crystallizations of a pair of homeomorphic but non-PL-homeomorphic 4-manifolds. In addition, we give an elementary proof that the minimal 8-vertex crystallization of CP2 is unique and its associated pseudotriangulation is related to the 9-vertex combinatorial triangulation of CP2 by the minimum of four edge contractions.

Tight triangulations of closed 3-manifolds

A triangulation of a closed 2-manifold is tight with respect to a field of characteristic two if and only if it is neighbourly; and it is tight with respect to a field of odd characteristic if and only if it is neighbourly and orientable. No such characterization of tightness was previously known for higher dimensional manifolds. In this paper, we prove that a triangulation of a closed 3-manifold is tight with respect to a field of odd characteristic if and only if it is neighbourly, orientable and stacked. In consequence, the Kuhnel-Lutz conjecture is valid in dimension three for fields of odd characteristic. Next let F be a field of characteristic two. It is known that, in this case, any neighbourly and stacked triangulation of a closed 3-manifold is F-tight. For closed, triangulated 3-manifolds with at most 71 vertices or with first Betti number at most 188, we show that the converse is true. But the possibility of the existence of an F-tight, non-stacked triangulation on a larger number of vertices remains open. We prove the following upper bound theorem on such triangulations. If an F-tight triangulation of a closed 3-manifold has n vertices and first Betti number beta(1), then (n - 4) (617n - 3861) <= 15444 beta(1). Equality holds here if and only if all the vertex links of the triangulation are connected sums of boundary complexes of icosahedra. (C) 2015 Elsevier Ltd. All rights reserved.

Fototriangulación aplicada a elementos patrimoniales

[ES] Existe una continuación de este trabajo realizada en 2014, cuyo título es:

L'Indépendance de l'empire du Brésil :présentée aux monarques européens

Alphonse de Beauchamp, historiador francês, nasceu em Mônaco, em 1767, e morreu em Paris, em 1832. Trabalhou no Departamento de Polícia como censor de imprensa. Organizou e publicou várias obras históricas.

Voyages dans la partie septentrionale du Bresil, depuis 1809 jusqu'en 1815, comprenant les provinces de Pernambuco, Fernambouc, Seara, Paraiba, Maragnan, etc.

Titulo original : travels in brazil : in the years from 1809, to 1815.

Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Aplicação das fórmulas de Vincenty nos cálculos das correções dos efeitos do relevo na gravidade e na altura geoidal.

O presente trabalho apresenta a aplicação das fórmulas de Vincenty nos cálculos das correções do terreno e do efeito indireto, que desempenham papel relevante na construção de cartas geoidais. Implementa-se um programa de processamento que realiza a integração numérica sobre o modelo digital do terreno, discretizado em células triangulares de Delaunay. O sistema foi desenvolvido com a linguagem de programação FORTRAN, para a execução de intensos algoritmos numéricos usando compiladores livres e robustos. Para o cálculo do efeito indireto, considera-se a redução gravimétrica efetuada com base no segundo método de condensação de Helmert, face ao pequeno valor de efeito indireto no cálculo do geóide, em função da mudança que este produz no potencial da gravidade devido ao deslocamento da massa topográfica. Utiliza-se, o sistema geodésico SIRGAS 2000 como sistema de referência para o cômputo das correções. Simplificando o exame dos resultados alcançados, distingue-se o processamento e desenvolvimento do trabalho em etapas como a escolha de ferramentas geodésicas para máxima precisão dos resultados, elaboração de subrotinas e comparação de resultados com cálculos anteriores. Os resultados encontrados foram de geração sadia e satisfatória e podem ser perfeitamente empregados no cálculo do geóide em qualquer área do globo.

Política Nacional de Educação Permanente no SUS: estudo da implantação sob a perspectiva dos gestores da Secretaria Municipal de Saúde de Teresópolis em 2006

Este estudo investigou a implementação da Política Nacional de Educação Permanente da Saúde (PNEPS) no Estado do Rio de Janeiro, durante o ano de 2006. A PNEPS, fundamentalmente, visa mudança das práticas de saúde por meio da educação permanente em serviço pela problematização do cotidiano do trabalho em saúde. No percurso da descentralização, preconizada tanto pelo Sistema Único de Saúde como pela PNEPS, o território de eleição para a investigação foi o do Município de Teresópolis, apresentado segundo os parâmetros utilizados para o cálculo do Índice de Desenvolvimento Humano. A pesquisa se concentrou na Secretaria Municipal de Saúde e nas rodas de consenso do Pólo de Educação Permanente em Saúde da Região Serrana do Estado do Rio de Janeiro. A metodologia utilizou a triangulação de dados procedentes das técnicas da observação participante, da consulta a fontes documentais pertinentes e de dez entrevistas semi-estruturadas feitas com gestores da Secretaria Municipal de Saúde. O material narrativo, das entrevistas, foi transcrito e submetido à análise do discurso. O campo aportou dados inusitados para a análise da implementação da PNEPS. Tanto a prefeitura como a UNIFESO compartilham da mesma liderança política, com repercussões na gestão do Sistema Único de Saúde e na educação formal em saúde. Embora o Programa de Saúde da Família gere demandas para a PNEPS, o cruzamento e a sobrecarga das ações assistenciais com as educativas, nesta instância, mediadas pelo mesmo profissional da saúde, também preceptor da UNIFESO, trazem repercussões para ambas as iniciativas. Principalmente, obstaculizam propostas educativas para as demandas de trabalhadores e de usuários. Finalmente, no que concerne às políticas públicas, o estudo demonstrou a presença do modelo centro-periferia em escala municipal, à semelhança daquele de dimensões mundial e federal, expresso pela descentralização de ações com centralização de recursos.

Trajetórias educacionais de crianças com necessidades especiais no município do Rio de Janeiro

O estudo tem como tema os Percursos trilhados pelas famílias para a garantia do direito à educação de crianças com necessidades especiais. Este estudo surgiu pela demanda dos integrantes do Núcleo de Estudos da Infância: Pesquisa & Extensão (NEI:P&E/UERJ), coordenado pela Prof Dr Vera Vasconcellos, em compreender como ocorreu a trajetória de escolarização de crianças acompanhadas em dois estudos realizados em creches do município do Rio de Janeiro, em 2009, após a saída delas das referidas instituições. Os estudos foram: i) Crianças focais: a triangulação educação-família-saúde na creche, realizado em 2008 e 2009 na Creche Institucional Dr. Paulo Niemeyer; e ii) Infância, Educação e Inclusão: um estudo de caso, realizado em 2009 na Creche Municipal de Odetinha Vidal de Oliveira. A pesquisa atual tem como proposta um estudo de follow-up, onde demos continuidade às duas anteriores, a partir da análise do percurso de três (3) famílias (mãe) na tentativa de garantir uma educação inclusiva de qualidade para seus filhos. Inicialmente, foi realizado um levantamento bibliográfico e documental sobre o tema. Em seguida voltou-se às famílias das crianças com o objetivo de investigar de que modo à escolarização foi sendo propiciadas a estas crianças e como suas dificuldades de aprendizagem têm sido entendidas nos espaços educacionais que frequentam. Adotamos o Estudo de Caso como proposta metodológica. Foram realizadas duas entrevistas com as mães das crianças, respectivamente em 2012 e 2013 e solicitado que elas respondessem um questionário (Caracterização Familiar), que delineava o perfil das mesmas destacando suas características sóciodemograficas. Os dados produzidos foram sistematizados através da abordagem de Análise de Conteúdo por temáticas, com ênfase nas trajetórias das crianças e suas famílias em prol da garantia ao direito à Educação. A pesquisa conclui que as crianças do estudo não encontraram espaço no sistema regular de educação, público e/ou privado, em contraste ao que garante os documentos nacionais e municipais. As trajetórias e experiências foram repletas de inseguranças e expectativas negativas por parte das escolas quanto ao desenvolvimento e escolarização das crianças. Conclui também que não é suficiente conhecer os direitos à educação da criança com necessidades especiais, as instituições precisam reconhecer os familiares como parceiros privilegiados na construção de alternativas para a produção de conhecimentos das crianças com necessidades especiais. Os dados demonstraram a importância social das escolas especiais no atendimento especializado de crianças com necessidades especiais. Os lugares ocupados por essas instituições são reconhecido pelas famílias como fundamental rede de apoio e suporte às crianças e famílias no processo de educação e inclusão escolar.