Two and Three Finger Caging of Polygons and Polyhedra

Multi-finger caging offers a rigorous and robust approach to robot grasping. This thesis provides several novel algorithms for caging polygons and polyhedra in two and three dimensions. Caging refers to a robotic grasp that does not necessarily immobilize an object, but prevents it from escaping to infinity. The first algorithm considers caging a polygon in two dimensions using two point fingers. The second algorithm extends the first to three dimensions. The third algorithm considers caging a convex polygon in two dimensions using three point fingers, and considers robustness of this cage to variations in the relative positions of the fingers.

This thesis describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on a contact-space formulation. It shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand’s configuration space appear as critical points of the inter-finger distance function in contact space. Second, these critical points can be graphically characterized directly on the object’s boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

A second algorithm is developed for finding caging formations of a 3D polyhedron for two point fingers using a lower dimensional contact-space formulation. Results from the two-dimensional algorithm are extended to three dimension. Critical points of the inter-finger distance function are shown to be identical to the critical points of the cage. A decomposition of contact space into 4D regions having useful properties is demonstrated. A geometric analysis of the critical points of the inter-finger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. With these properties established, the search algorithm from the two-dimensional case may be applied to the three-dimensional problem. An implemented example demonstrates the method.

This thesis also presents a study of cages of convex polygonal objects using three point fingers. It considers a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. It analyzes robustness of caging grasps to variations in the relative position of the fingers without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages.

Heavy metal contents in Fe-Mn nodules and crusts from R/V Vityaz polygons and stations in the East Indian Ocean

Regional variations in abundance, morphology, and chemical composition of Fe-Mn nodules have a zonal character. Due to circumcontinental zonality of terrigenous sedimentation the main mass of the nodules occurs in the pelagic part of the ocean, in areas of minimal sedimentation rates. In spatial variations in morphology and chemical composition of the nodules the latitudinal zonality is very clear and associated with latitudinal changes in facial conditions of sedimentation. Elevated contents of Mn, Ni, and Cu and of Mn/Fe ratio occur in nodules from the radiolarian belt. Changes of chemical composition of the nodules with depth (vertical zonality of mineralization) are confirmed. Local variations in abundance, morphology and chemical composition of the nodules are caused by ruggedness of relief and depth variations, variations in sedimentation rate, age of ore formation, intensity of diagenetic redistribution of metals.

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.

O conhecimento de polígonos e poliedros: uma análise do desempenho de alunos do ensino médio em exemplos e não-exemplos

O artigo pretende mostrar os resultados de uma pesquisa cujo objetivo foi analisar o desempenho de alunos do Ensino Médio na identificação de exemplos e não-exemplos de polígonos e poliedros, tendo em vista os atributos definidores e atributos irrelevantes. Participaram da pesquisa 253 alunos, distribuídos em três séries do Ensino Médio de uma escola pública, que responderam um teste de exemplos e não-exemplos. Posteriormente, foram selecionados seis alunos para serem entrevistados sobre seus conhecimentos a respeito dos exemplos e não-exemplos. Os resultados mostraram que os participantes obtiveram uma média baixa (M = 5,59) na tarefa que exigiu a identificação de exemplos e não-exemplos de polígonos e poliedros. A análise das entrevistas mostrou que a maioria dos alunos considerou que o atributo irrelevante dos polígonos analisados não interferiu na resposta. Contudo, evidencia-se, de modo geral, que esses alunos apresentaram um conhecimento conceitual longe do esperado para esse nível de ensino.

Um estudo exploratório sobre a formação conceitual em geometria de alunos do ensino médio

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Characterizing and recognizing weak visibility polygons

A polygon is said to be a weak visibility polygon if every point of the polygon is visible from some point of an internal segment. In this paper we derive properties of shortest paths in weak visibility polygons and present a characterization of weak visibility polygons in terms of shortest paths between vertices. These properties lead to the following efficient algorithms: (i) an O(E) time algorithm for determining whether a simple polygon P is a weak visibility polygon and for computing a visibility chord if it exist, where E is the size of the visibility graph of P and (ii) an O(n2) time algorithm for computing the maximum hidden vertex set in an n-sided polygon weakly visible from a convex edge.

Ensino-aprendizagem de geometria: uma proposta fazendo uso de caleidoscópios, sólidos geométricos e softwares educacionais

Pós-graduação em Educação Matemática - IGCE

Volcanic terrain and the possible periglacial formation of "excess ice" at the mid-latitudes of Utopia Planitia, Mars

At the mid-latitudes of Utopia Planitia (UP), Mars, a suite of spatially-associated landforms exhibit geomorphological traits that, on Earth, would be consistent with periglacial processes and the possible freeze-thaw cycling of water. The suite comprises small-sized polygonally-patterned ground, polygon-junction and -margin pits, and scalloped, rimless depressions. Typically, the landforms incise a dark-toned terrain that is thought to be ice-rich. Here, we investigate the dark-toned terrain by using high resolution images from the HiRISE as well as near-infrared spectral-data from the OMEGA and CRISM. The terrain displays erosional characteristics consistent with a sedimentary nature and near-infrared spectra characterised by a blue slope similar to that of weathered basaltic-tephra. We also describe volcanic terrain that is dark-toned and periglacially-modified in the Kamchatka mountain-range of eastern Russia. The terrain is characterised by weathered tephra inter-bedded with snow, ice-wedge polygons and near-surface excess ice. The excess ice forms in the pore space of the tephra as the result of snow-melt infiltration and, subsequently, in-situ freezing. Based on this possible analogue, we construct a three-stage mechanism that explains the possible ice-enrichment of a broad expanse of dark-toned terrain at the mid-latitudes of UP: (1) the dark-toned terrain accumulates and forms via the regional deposition of sediments sourced from explosive volcanism; (2) the volcanic sediments are blanketed by atmospherically-precipitated (H2O) snow, ice or an admixture of the two, either concurrent with the volcanic-events or between discrete events; and, (3) under the influence of high obliquity or explosive volcanism, boundary conditions tolerant of thaw evolve and this, in turn, permits the migration, cycling and eventual formation of excess ice in the volcanic sediments. Over time, and through episodic iterations of this scenario, excess ice forms to decametres of depth. (C) 2015 Elsevier B.V. All rights reserved.

Radiocarbon ages and diatom abundance in samples obtained from Qarlikturvik Valley, Bylot Island

The formation of many arctic wetlands is associated with the occurrence of polygon-patterned permafrost. Existing scenarios to describe and explain surface landforms in arctic wetlands (low-center and high-center polygons and polygon ponds) invoke competing hypotheses: a cyclic succession (the thaw-lake hypothesis) or a linear succession (terrestrialization). Both hypotheses infer the predictable development of polygon-patterned wetlands over millennia. However, very few studies have applied paleoecological techniques to reconstruct long-term succession in tundra wetlands and thereby test the validity of existing hypotheses. This paper uses the paleoecological record of diatoms to investigate long-term development of individual polygons in a High Arctic wetland. Two landform processes were examined: (1) the millennial-scale development of a polygon-pond, and (2) the transition from low-center to erosive high-center polygons. Diatom assemblages were quantified from habitats associated with contrasting landforms in the present-day landscape, and used as an analog to reconstruct past transitions between polygon types. On the basis of this evidence, the paleoecological record does not support either of the existing models describing the predictable succession of polygon landforms in an arctic wetland. Our results indicate a need for greater paleoecological understanding, in combination with in situ observations in present-day geomorphology, in order to identify patterns of polygon wetland development and elucidate the long-term drivers of these landform transitions.

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.

On the Erdos-Szekeres n-interior-point problem

The n-interior-point variant of the Erdos Szekeres problem is the following: for every n, n >= 1, does there exist a g(n) such that every point set in the plane with at least g(n) interior points has a convex polygon containing exactly n interior points. The existence of g(n) has been proved only for n <= 3. In this paper, we show that for any fixed r >= 2, and for every n >= 5, every point set having sufficiently large number of interior points and at most r convex layers contains a subset with exactly n interior points. We also consider a relaxation of the notion of convex polygons and show that for every n, n >= 1, any point set with at least n interior points has an almost convex polygon (a simple polygon with at most one concave vertex) that contains exactly n interior points. (C) 2013 Elsevier Ltd. All rights reserved.

a real-time path planning approach without the computation of cspace obstacles

An important concept proposed in the early stage of robot path planning field is the shrinking of the robot to a point and meanwhile expanding of the obstacles in the workspace as a set of new obstacles. The resulting grown obstacles are called the Configuration Space (Cspace) obstacles. The find-path problem is then transformed into that of finding a collision free path for a point robot among the Cspace obstacles. However, the research experiences obtained so far have shown that the calculation of the Cspace obstacles is very hard work when the following situations occur: 1. both the robot and obstacles are not polygons and 2. the robot is allowed to rotate. This situation is even worse when the robot and obstacles are three dimensional (3D) objects with various shapes. Obviously a direct path planning approach without the calculation of the Cspace obstacles is strongly needed. This paper presents such a new real-time robot path planning approach which, to the best of our knowledge, is the first one in the robotic community. The fundamental ideas are the utilization of inequality and optimization technique. Simulation results have been presented to show its merits.

Investigação em formação conceitual: o conhecimento de alunos do ensino médio sobre polígonos

This study is part of the area of research in Psychology of Mathematics Education that investigates, among other things, knowledge relating to the formation of mathematical concepts. The objective was to investigate the conceptual knowledge of polygons of 76 high school students in terms of defining attributes and examples and non-examples. The instruments for collecting data was a test with two questions about polygons, defining attributes of a test and a test of examples and non-examples, based on the theory of Klausmeier and Goodwin (1977) on formation of concepts. The results showed that participants of the survey had difficulties in identifying defining attributes of polygons and non-discriminating examples of examples, showing the formation of this concept to the level of identity.

Uso de dados fotogramétricos no refinamento geométrico de contornos de telhados de edifícios extraídos de dados laser

In this paper, a methodology is proposed for the geometric refinement of laser scanning building roof contours using high-resolution aerial images and Markov Random Field (MRF) models. The proposed methodology takes for granted that the 3D description of each building roof reconstructed from the laser scanning data (i.e., a polyhedron) is topologically correct and that it is only necessary to improve its accuracy. Since roof ridges are accurately extracted from laser scanning data, our main objective is to use high-resolution aerial images to improve the accuracy of roof outlines. In order to meet this goal, the available roof contours are first projected onto the image-space. After that, the projected polygons and the straight lines extracted from the image are used to establish an MRF description, which is based on relations ( relative length, proximity, and orientation) between the two sets of straight lines. The energy function associated with the MRF is minimized by using a modified version of the brute force algorithm, resulting in the grouping of straight lines for each roof object. Finally, each grouping of straight lines is topologically reconstructed based on the topology of the corresponding laser scanning polygon projected onto the image-space. The preliminary results showed that the proposed methodology is promising, since most sides of the refined polygons are geometrically better than corresponding projected laser scanning straight lines.

Aprendizagem de conceitos geométricos pelo futuro professor das séries iniciais do Ensino Fundamental e as novas tecnologias

Com o movimento da Matemática Moderna, a partir de 1950, o ensino da matemática passou a enfatizar o simbolismo e a exigir dos alunos grandes abstrações, distanciando a matemática da vida real. O que se percebe é que o aluno formado por este currículo aprendeu muito pouco de geometria e não consegue perceber a relação deste conteúdo com sua realidade. Por outro lado, o professor que não conhece geometria não consegue perceber a beleza e a importância que a mesma possui para a formação do cidadão. A geometria estimula a criança a observar, perceber semelhanças, diferenças e a identificar regularidades. O objetivo deste trabalho é identificar o nível de conhecimento dos alunos do Centro Específico de Formação e Aperfeiçoamento ao Magistério (CEFAM), futuros professores da 1ª a 4ª séries do Ensino Fundamental do Estado de São Paulo, quanto aos conceitos de ponto, reta, plano, ângulos, polígonos e circunferências e também verificar as contribuições do computador para a construção de conceitos geométricos. Para atingir esses objetivos, foi desenvolvida uma pesquisa com 30 alunos do CEFAM de Presidente Prudente-SP, na qual, com base no diagnóstico das dificuldades de aprendizagem, organizaram e desenvolveram-se os momentos de formação, que utilizaram o computador como ferramenta de aprendizagem e projetos de trabalho tendo como aporte teórico a abordagem construcionista. O futuro professor que não dominar a geometria e não perceber sua relação com a natureza não conseguirá contribuir para o desenvolvimento do pensamento geométrico da criança. Esse pensamento é que permite a criança observar, compreender, descrever e representar, de forma organizada, o mundo em que vive.