A range space (P, S) consists of a set P of n elements and a collection S = {S1,...,Sm} of subsets of P , referred to as ranges. A hitting set for this range space refers to a subset H of P such that every Si in S contains at least one element of H. The hitting set problem is studied for many geometric range spaces where P is a set of n points in Rd and the ranges are defined by the intersection of geometric objects with P . The algorithmic question of finding the minimum-sized hitting set for a given range space is well studied and is NP-Complete even for geometric range spaces defined by unit disks. The dual of the hitting set problem is the equally well studied set cover problem. A set cover is a sub-collection C⊆S such that every element in P is contained in at least one range in C. A classic problem which is related to the minimum set cover problem is the maximum coverage problem. In this problem, given a range space (P, S) and an integer k, we have to find k ranges from S such that the number of elements in P that are covered by these k ranges are maximized. In this thesis, we study combinatorial questions on a similar variant of hitting set problem for specific geometric range spaces where the size of the hitting set is fixed as a small constant. We study the small hitting set problem mainly for two broad classes of range spaces. We first consider the Dense range space (P, S) where P is a set of n points in Rd and S is defined by “dense” geometric objects i.e, geometric objects that contain more than a constant fraction, say �, of points from P . We fix the size of the hitting set as a small constant k and investigate bounds on the value of � such that all ranges that contain more than �n points from P are hit. Next we consider the Induced range space (P, I) where P isa setof n points in R2 and the ranges are all geometric objects that are induced(spanned) by P i.e., the ranges are defined by geometric objects that have a distinct tuple of points from P on its boundary. For Induced range spaces, we prove bounds on the maximum number of ranges that can be hit using a single point. We also prove combinatorial bounds on the size of the hitting set for various families of induced objects. Now, we describe the problems that we study in this thesis and summarize the results obtained. 1. Strong centerpoints: Here we study the small hitting set question for dense range spaces when the size of hitting set is one. This is related to a classic result in geometry called Centerpoint Theorem. A point x ∈ Rd is said to be the centerpoint of P if x is contained in all convex objects that contain more than dn points from P . Centerpoint Theorem states d+1 that a centerpoint always exists for any point set P . A centerpoint need not be an input point. A natural question to ask is the following: Does there exist a strong centerpoint? i.e., is it true that for any given point set P there exists a point p ∈ P such that p is contained in every convex object that contains more than a constant fraction, say �, of points of P ? It can be easily seen that a strong centerpoint does not exist even for geometric range spaces defined by half spaces. We study the existence and the corresponding bounds for strong centerpoints for some range spaces. In particular, we prove the existence of strong centerpoint and show tight bounds for the following range spaces. Convex polytopes defined by a fixed set of orientations : Geometric range spaces like those induced by axis-parallel boxes, skylines and downward facing equilateral triangles belong to this family of convex polytopes. Hyperplanes in Rd Range spaces with discrete intersection 2. Small Strong Epsilon Nets: This can be considered as an extension of strong centerpoints. This question is related to a well studied area called �-nets. N ⊂ P is called a (strong) �-net of P with respect to S if N ∩ S =�∅ for all objects S ∈S that contain more than �n points of P . We study the following question. Let �S∈ [0, 1] represent the smallest real number such that, for any given point set P , there exists Q ⊂ P of size i which is an �S-net with respect to S. Thus a strong centerpoint will be an �S1 -net. We prove bounds on �Si for small values of i where S is the family of axis-parallel rectangles, halfspaces and disks. 3. Strong First Selection Lemma: Here we consider the hitting question for induced range spaces when the size of the hitting set is one. In other words, given an induced range space, we prove bounds on the maximum number of ranges that can be hit using a single input point. Such questions are referred to as First Selection Lemma and are well studied. We consider the strong version of the First Selection Lemma where the “heavily covered” point is required to be an input point. We study the strong first selection lemma for induced rectangles, induced special rectangles and induced disks. We prove an exact result for the strong variant of the first selection lemma for axis-parallel rectangles. We also prove exact results for the strong variant of the first selection lemma for some subclasses of axis-parallel rectangles like orthants and slabs. We prove strong first selection lemma with almost tight bounds for skylines, another sub-class of axis-parallel rectangles. We prove bounds for first selection lemma for disks in the plane and exact results for a special case when the discs are induced by a centrally symmetric point set. 2 Hitting all Induced Objects: Here we discuss and prove combinatorial bounds on the size of the minimum hitting set for induced range spaces. We prove tight bounds on the hitting set size when induced objects are special rectangles, disks and downward facing equilateral triangles.

Made available in DSpace on 2016-04-27T16:57:41Z (GMT). No. of bitstreams: 1 Elisabete Marcon Mello.pdf: 3241928 bytes, checksum: c959f6d01b98b9dcf17222cbb7877b00 (MD5) Previous issue date: 2015-12-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This thesis aimed to investigate how blind students visualize geometric objects, based on the Theory of Semiotics Representation, Vision and View Registers of Raymond Duval. Checking the official documents that determine the course of education, we found that they establish that children and young people with special educational needs must have access to schools, preferably in the regular school system, which must be suitable to them, both materially and educationally. So, we performed a case study in a public school in the city of Santo André, São Paulo, which has blind students attending ordinary classrooms. Through interviews, we investigated how congenitally blind students recognize and work with representations of geometric objects and what are the possibilities of these students create their own representations on paper. We found that the interviewed students identified flat geometric figures embossed on paper, recognizing their forms, but didn t recognize the geometric solids representations in perspective, because the outline of these objects does not match with their outline on paper. We note the need to teach how to visualize, it is necessary that the blind students learn how to identify the represented object in each representation, this recognition is not automatic but it can be learned. We noted that the order of perception by touching is different when the blind student has a concrete object in his hands and when it has a representation of this object embossed on paper. When the blind student has a concrete object in his hands, and this object is familiar to him, he recognizes the entire object without the need to observe the parts, but when the representation is embossed on paper, even if the student knows the represented object, he visualizes the parts first and then the entire object. In the interviews, we witnessed times when the students reached the perceptual, operative and discursive apprehensions, despite having a very limited repertoire of geometric terms. One of the students operated the dimensional deconstruction of the forms and could "see" mathematically, as mentioned by Duval (2011). None of the students we interviewed had ever built or designed geometric figures in a way that after they could recognize them, so the sequential apprehension that aims at the construction of geometric figures was not observed during our investigation. Seeking to fill this gap, we propose the creation of the Drawing on Positive Relief Clipboard, with which a blind student has the possibility to design and feel the design embossed on paper / Esta tese teve por objetivo investigar como alunos cegos visualizam objetos geométricos, embasada na Teoria dos Registros de Representação Semiótica, Visão e Visualização de Raymond Duval. Verificando os documentos oficiais que determinam os rumos da educação, constatamos que eles estabelecem que as crianças e jovens com necessidades educacionais especiais devem ter acesso às escolas, preferencialmente na rede regular de ensino, que devem estar adequadas a eles, tanto material quanto pedagogicamente. Nesse sentido, realizamos um estudo de caso em uma escola pública estadual da cidade de Santo André, São Paulo, que tem alunos cegos frequentando as salas de aula comuns. Por meio de entrevistas, investigamos como alunos cegos congênitos reconhecem e trabalham com representações de objetos geométricos e quais as possibilidades desse aluno criar suas próprias representações no papel. Verificamos que os alunos entrevistados identificaram figuras geométricas planas, representadas em relevo, no papel, reconhecendo suas formas, mas não reconheceram representações de sólidos geométricos em perspectiva, pois o contorno desses objetos não corresponde ao contorno de sua representação no papel. Constatamos a necessidade de ensinar a visualizar, é preciso que o aluno cego aprenda a identificar em cada representação o objeto representado, esse reconhecimento não é automático, mas pode ser aprendido. Observamos que a ordem de percepção pelo tato é diferente quando o aluno cego tem um objeto concreto em suas mãos e quando tem uma representação deste objeto em relevo no papel. Quando o aluno cego tem um objeto concreto em suas mãos, e este objeto lhe é familiar, ele reconhece o todo, sem necessidade de observar as partes, mas, quando a representação está em relevo no papel, mesmo que o aluno conheça o objeto representado, ele visualiza primeiro as partes para depois visualizar o todo. Nas entrevistas, presenciamos momentos em que alunos atingiram as apreensões perceptiva, operatória e discursiva, apesar de apresentarem um repertório muito limitado de termos geométricos. Um dos alunos operou a desconstrução dimensional das formas e pôde ver matematicamente, como mencionado por Duval (2011). Nenhum dos alunos que entrevistamos já havia construído ou desenhado figuras geométricas de forma que pudesse reconhecê-las, portanto, a apreensão sequencial, que tem por objetivo a construção de figuras geométricas, não foi observada durante nossa investigação. Procurando preencher essa lacuna, propomos a criação da Prancheta de Desenho em Relevo Positiva, com a qual um aluno cego tem a possibilidade de desenhar e sentir o desenho em relevo no papel

In this thesis we consider extensions and generalizations of some classical problems in Combinatorial Geometry. Our work is an offshoot of four classical problems in Combinatorial Geometry. A fundamental assumption in these problems is that the underlying point set is R2. Two fundamental themes entwining the problems considered in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since. Avis et al. in 2001 posed the following question which we call the n-interior point problem: Is there a finite integer g(n) for every n, such that, every point set P with g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset which is a convex polygon that contains exactly n interior points. They showed that g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers. We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed the following fundamental question which can be considered as a generalised version of Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known. Inspired by the original question of Danzer and Gr¨unbaum we consider their question in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting. In the third part of this thesis, we broadly look at hitting and covering questions with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively. These problems has been well studied in the case when P = R2. We systematically look at the case when P is finite, showing bounds for intervals, halfspaces, orthants, unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2. Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express the bound on the size of the set Q in terms of ǫ. Let G be a uniform √n × √n grid. It is an intriguing question as to whether we get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.

No description available.

This text discusses final results from empirical studies, scientific articles and literature from the period 1990-2023, concerning teachers’ knowledge, students’ misconceptions and various teaching methods related to geometric objects. The results highlight challenges for both teachers and students in understanding and defining geometric shapes and figures. The work elucidates students in grade 4-6 difficulties and knowledge in identifying geometric objects in varied positions, as well as their understanding of the properties of geometric shapes and figures. The teacher’s understanding is crucial för imparting accurate information to students in instruction. Therefore, effective teaching methods such as practical activities, everyday connection and Van Hiele’s instructional model are suitable to apply in practice. This instructional model has been effective in students education and is therefore a good example for a teaching method.  In summary, the results are based on the abilities of teachers and students and their abilities can be enhanced by adapting teaching methods related to geometric objects, and how misconceptions are something that should be taken seriously and be prevented.

Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph.