Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Some results on open-edge and open mobile guarding of polygons and triangulations

This paper focuses on a variation of the Art Gallery problem that considers open-edge guards and open mobile-guards. A mobile guard can be placed on edges and diagonals of a polygon, and the ‘open’ prefix means that the endpoints of such an edge or diagonal are not taken into account for visibility purposes. This paper studies the number of guards that are sufficient and sometimes necessary to guard some classes of simple polygons for both open-edge and open mobile-guards. A wide range of polygons is studied, which include orthogonal polygons with or without holes, spirals, orthogonal spirals and monotone polygons. Moreover, this problem is also considered for planar triangulation graphs using open-edge guards.

Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

Representação da área de responsabilidade de jogadores de futebol através do Diagrama de Voronoi

Universidade Estadual de Campinas . Faculdade de Educação Física

Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular two dimensional polygons inside a two dimensional container. This problem is approached with an heuristic based on simulated annealing. Traditional 14 external penalization"" techniques are avoided through the application of the no-fit polygon, that determinates the collision free area for each polygon before its placement. The simulated annealing controls: the rotation applied, the placement and the sequence of placement of the polygons. For each non placed polygon, a limited depth binary search is performed to find a scale factor that when applied to the polygon, would allow it to be fitted in the container. It is proposed a crystallization heuristic, in order to increase the number of accepted solutions. The bottom left and larger first deterministic heuristics were also studied. The proposed process is suited for non convex polygons and containers, the containers can have holes inside. (C) 2009 Elsevier Ltd. All rights reserved.

HIV heterogeneity and proximity of homestead to roads in rural South Africa: an exploration using a geographical information system

OBJECTIVE To describe heterogeneity of HIV prevalence among pregnant women in Hlabisa health district, South Africa and to correlate this with proximity of homestead to roads. METHODS HIV prevalence measured through anonymous surveillance among pregnant women and stratified by local village clinic. Polygons were created around each clinic, assuming women attend the clinic nearest their home. A geographical information system (GIS) calculated the mean distance from homesteads in each clinic catchment to nearest primary (1 degrees) and to nearest primary or secondary (2 degrees) road. RESULTS We found marked HIV heterogeneity by clinic catchment (range 19-31% (P < 0.001). A polygon plot demonstrated lower HIV prevalence in catchments remote from 1 degrees roads. Mean distance from homesteads to nearest 1 degrees or 2 degrees road varied by clinic catchment from 1623 to 7569 m. The mean distance from homesteads to a 1 degrees or 2 degrees road for each clinic catchment was strongly correlated with HIV prevalence (r = 0.66; P = 0.002). CONCLUSIONS The substantial HIV heterogeneity in this district is closely correlated with proximity to a 1 degrees or 2 degrees road. GIS is a powerful tool to demonstrate and to start to analyse this observation. Further research is needed to better understand this relationship both at ecological and individual levels, and to develop interventions to reduce the spread of HIV infection.

A Comparison of the Home Range Sizes of Mainland and Island Populations of Black-Faced Lion Tamarins (Leontopithecus caissara) Using Different Spatial Analysis

The critically endangered black-faced lion tamarin, Leontopithecus caissara, has a restricted geographical distribution consisting of small mainland and island populations, each with distinct habitats in coastal southeastern Brazil. Necessary conservation management actions require an assessment of whether differences in habitats are reflected in use of space by the species. We studied two tamarin groups on the mainland at Sao Paulo state between August 2005 and March 2007, and compared the results with data from Superagui Island. Three home range estimators were used: minimum convex polygon (MCP), Kernel, and the new technique presented dissolved monthly polygons (DMP). These resulted, respectively, in home ranges of 345, 297, and 282 ha for the 12-month duration of the study. Spatial overlap of mainland groups was extensive, whereas temporal overlap was not, a pattern that indicates resource partitioning is an important strategy to avoid intraspecific competition. L. caissara large home ranges seem to be dynamic, with constant incorporation of new areas and abandonment of others through time. The main difference between mainland and island groups is the amount and variety of sleeping sites. A better understanding of the home range sizes, day range lengths, and territorial behavior of this species will aid in developing better management strategies for its protection. Additionally, the presented DMP protocol is a useful improvement over the MCP method as it results in more realistic home range sizes for wildlife species. Am. J. Primatol. 73: 1114-1126, 2011. (C) 2011 Wiley Periodicals, Inc.

Abordagens metodológicas para avaliar risco de extinção de espécies de Brachyteles (Primates : Atelidae)

A distribuição geográfica de um táxon é limitada por aspectos ecológicos e históricos. Muitas atividades humanas têm causado modificações na cobertura vegetal, o que leva à fragmentação e perda do habitat. Isso tem levado à extinção local de populações de várias espécies, alterando sua distribuição geográfica. Entre elas estão as duas espécies do gênero Brachyteles (os muriquis), que são primatas endêmicos de um dos biomas mais afetados por esses processos, a Mata Atlântica. A União Internacional para a Conservação da Natureza (UICN) é uma organização que busca conservar a biodiversidade. Entre outros critérios, utiliza o conhecimento sobre as distribuições geográficas restritas das espécies para classificá-las em categorias de ameaça de extinção, nas chamadas listas vermelhas. Para isso, utiliza parâmetros espaciais, cujos resultados indicam o risco de extinção de determinado táxon em relação à sua distribuição geográfica. Muitas vezes os cálculos desses parâmetros são realizados de maneira subjetiva, de maneira que é importante a busca de métodos que tornem as classificações mais objetivas, precisas e replicáveis. Nesse contexto, o presente trabalho testou diferentes métodos de cálculos de três parâmetros relacionados à distribuição geográfica de B. hypoxanthus e B. arachnoides. Tratam-se de espécies ameaçadas de extinção, com localidades de ocorrência bem conhecidas, que foram profundamente afetadas pela degradação da Mata Atlântica. Assim, podem ser consideradas bons modelos para essas análises. Foi construído um banco de dados de localidades de ocorrência atuais das duas espécies. Por meio de abordagens de Sistemas de Informação Geográfica (SIG), foram estimadas a Extensão de Ocorrência (EOO) através de Mínimo Polígono Convexo e α-hull e Área de Ocupação (AOO) e Subpopulações por meio de métodos de grids, buffers circulares e α-hull, em diferentes escalas espaciais. Os resultados dos cálculos desses parâmetros foram comparados para identificar as abordagens e escalas mais adequadas para a avaliação de risco de extinção. Esses resultados indicam que as listas de localidades e os mapas de distribuição disponibilizados pela UICN precisam ser atualizados. Além disso, sugerem que α-hull é uma abordagem vantajosa para EOO e o método de buffers é mais adequado para os parâmetros de AOO e Subpopulações, quando utiliza escalas espaciais menores. Também foi utilizada a ferramenta GeoCAT, para as duas espécies. Essa ferramenta, por realizar análises de EOO e AOO instantâneas e por seus resultados serem semelhantes aos de outras análises, serve como uma abordagem preliminar de risco de extinção baseado no critério de distribuição geográfica.

Algumas técnicas SIG úteis à obtenção de áreas de serviço de conjuntos de pontos

Em estudos de acessibilidade, e não só, são muito úteis um tipo de estruturas que se podem obter a partir de uma rede, eventualmente multi-modal e parametrizável: as chamadas “áreas de serviço”, as quais são constituídas por polígonos, cada qual correspondente a uma zona situada entre um certo intervalo de custo, relativamente a uma certa “feature” (ponto, multiponto, etc.). Pretende-se neste estudo obter, a partir de áreas de serviço relativas a um universo de features, áreas de serviço relativas a subconjuntos dessas features. Estas técnicas envolvem manipulações relativamente complexas de polígonos e podem ser generalizadas para conjuntos de conjuntos e assim sucessivamente. Convém notar que nem sempre se dispõe da rede, podendo dispor-se das referidas estruturas; eventualmente, no caso de áreas de serviço, sob a forma de imagens (raster) a serem convertidas para formato vectorial.

Reasoning and proof in classroom (9th grade)

This paper is research oriented and pretends to contribute toward giving empirical evidence about how students develop their reasoning and how they achieved to a proof construction in school context. Its main theme is epistemology. It describes the way in which four students in 9th Grade explored a task related with the discovery of symmetry axes in various geometric figures. The proof constructed by students had essentially an explaining function and it was related with the symmetry axes of regular polygons. The teacher’s role in meaning negotiation of the proof and its need is described through illustrative episodes. The paper presents part of a study which purpose is to analyse the nature of mathematical proof in classroom, its role and the nature of the relationship between the construction of a proof and the social interactions. Assuming a social perspective, attention is focussed on the social construction of knowledge and on the structuring resources that shape mathematical experience. The study’s methodology has an interpretative nature. One outcome of the study discussed here is that students develop first a practical understanding with no awareness of the reasons founding mathematical statements and after a theoretical one leading them to a proof elaboration.

Desenvolvimento de um plano de manutenção preventiva na rede de distribuição de água de Lisboa

O presente relatório de estágio enquadra-se no âmbito do trabalho final de Mestrado do curso de Engenharia Civil, área de especialização em Hidráulica, do Instituto Superior de Engenharia de Lisboa, e incide na temática dos sistemas de distribuição de água. O estágio decorreu na empresa EPAL – Empresa Portuguesa das Águas Livres, S.A., e teve como objecto o desenvolvimento de um plano de manutenção preventiva para a rede de distribuição de água de Lisboa. Devido à crescente complexidade dos sistemas de abastecimento de água e à grande dispersão territorial dos diversos órgãos integrados na rede, surge a necessidade de desenvolver um sistema que permita simplificar o planeamento e a gestão das intervenções de inspecção e manutenção preventiva dos órgãos. Para esse efeito, recorreu-se a um software SIG (Sistema de Informação Geográfica) para proceder à sectorização da rede de distribuição de água em pequenos grupos (Polígonos), constituídos por um número determinado de órgãos de manobra e segurança. Esta metodologia permite organizar as intervenções em pequenos grupos e optimizar as rotinas de Inspecção diárias. No decorrer do estágio efectuou-se ainda um levantamento dos procedimentos de inspecção e manutenção dos diversos órgãos integrados na rede de distribuição de água de Lisboa, quer por acompanhamento de actividades com as equipas de inspecção, quer por recolha de recomendações junto dos fabricantes dos órgãos. Este levantamento permitiu elaborar fichas de procedimento para as actividades de inspecção e manutenção preventiva dos diversos órgãos, afim de serem usadas como referência pelos trabalhadores.

Desenvolvimento do conceito de ângulo: um estudo no 5.ºano de escolaridade

A investigação em curso visa compreender a influência da implementação de um conjunto de tarefas no desenvolvimento do conceito de ângulo em alunos do 5.º ano de escolaridade, procurando responder às seguintes questões: a) Que conceções revelam alunos do 5.º ano de escolaridade relativamente ao conceito de ângulo?; b) Que estratégias utilizam os alunos do 5.º ano de escolaridade na exploração das tarefas utilizadas?; e c) Que aspetos do conceito de ângulo são desenvolvidos pelos alunos através da realização das tarefas propostas? A presente comunicação incide na primeira questão do estudo. Optou-se por uma abordagem metodológica qualitativa de paradigma interpretativo com a modalidade de experiência de ensino. Selecionou-se quatro alunos para constituir o grupo-alvo. Procedeu-se à avaliação diagnóstica das conceções de ângulo dos quatro alunos através da realização, no 1.º Período do ano letivo de 2011/12, de entrevistas clínicas semiestruturadas individuais, gravadas em vídeo. Além das entrevistas, foram usadas, como técnicas de recolha de dados, a observação participante das aulas, videogravadas, bem como a análise de documentos. Para analisar os dados, foram elaboradas categorias analíticas. Os resultados relativos à avaliação diagnóstica evidenciam conceções erradas de ângulo e respetiva amplitude: (a) os ângulos são os lados de polígonos (1 aluna); (b) o comprimento dos segmentos representativos dos lados está relacionado com o tamanho dos ângulos (2 alunos); (c) o comprimento do arco marcando o ângulo está relacionado com o tamanho dos ângulos (3 alunos); (d) nos polígonos côncavos, sãoângulos apenas os de amplitude inferior a 1800 (3 alunos); (e) em figuras que não são polígonos, os ângulos são os espaços entre os segmentos de reta e as linhas curvas (1 aluno); (f) o ângulo é a área entre dois segmentos representativos dos lados (4 alunos); e (g) os ângulos retos são apenas os posicionados na posição usual horizontal/vertical (1 aluna).

Distributed Forest Fire Monitoring Using Wireless Sensor Networks

Disaster management is one of the most relevant application fields of wireless sensor networks. In this application, the role of the sensor network usually consists of obtaining a representation or a model of a physical phenomenon spreading through the affected area. In this work we focus on forest firefighting operations, proposing three fully distributed ways for approximating the actual shape of the fire. In the simplest approach, a circular burnt area is assumed around each node that has detected the fire and the union of these circles gives the overall fire’s shape. However, as this approach makes an intensive use of the wireless sensor network resources, we have proposed to incorporate two in-network aggregation techniques, which do not require considering the complete set of fire detections. The first technique models the fire by means of a complex shape composed of multiple convex hulls representing different burning areas, while the second technique uses a set of arbitrary polygons. Performance evaluation of realistic fire models on computer simulations reveals that the method based on arbitrary polygons obtains an improvement of 20% in terms of accuracy of the fire shape approximation, reducing the overhead in-network resources to 10% in the best case.

Об единственности решения обратной задачи теории потенциала для круговых многоугольников

სტატიაში დამტკიცებულია წრიული მრავალკუთხედებისათვის შებრუნებული ამოცანის ამოხსნის ერთადერთობა ორი შემთხვევისათვის: პირველი მუდმივი სიმკვრივისა და მეორე დადებითი სიმკვრივისათვის, რომელიც არ იცვლება მიმართულების მიხედვით.