No description available.

Thesis (Ph. D.)--University of North Texas, May, 2009. / Title from title page display. Includes bibliographical references.

Thesis (Ph. D.)--University of Washington, 2001. / Vita. Includes bibliographical references (p. 69-73).

Thesis (B.A.)--Haverford College, Dept. of Mathematics, 2002. / Includes bibliographical references.

In this paper we establish the existence and partial regularity of a (d-2)-dimensional edge-length minimizing polyhedron in [Special characters omitted.] . The minimizer is a generalized convex polytope of volume one which is the limit of a minimizing sequence of polytopes converging in the Hausdorff metric. We show that the (d-2)-dimensional edge-length ζ d -2 is lower-semicontinuous under this sequential convergence. Here the edge set of the limit generalized polytope is a closed subset of the boundary whose complement in the boundary consists of countably many relatively open planar regions.

The problem of computing the minimum distance between two convex hulls has applications to many areas including robotics, computer graphics and path planning. Moreover, determining the minimum distance between two convex hulls plays a significant role in support vector machines (SVM). In this study, a new algorithm for finding the minimum distance between two convex hulls is proposed and investigated. A convergence of the algorithm is proved and applicability of the algorithm to support vector machines is demostrated. The performance of the new algorithm is compared with the performance of one of the most popular algorithms, the sequential minimal optimization (SMO) method. The new algorithm is simple to understand, easy to implement, and can be more efficient than the SMO method for many SVM problems.

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.

Le polytope des m-sous-espaces est défini comme l'enveloppe convexe des vecteurs caractéristiques de tous les sous-espaces de dimension m d'un espace affin fini. Le cas particulier du polytope des hyperplans a été étudié par Maurras (1993) et Anglada et Maurras (2003), qui ont obtenu une description complète des facettes. Le polytope général des m-sous-espaces que nous considérons possède une structure plus complexe, notamment concernant les facettes. Néanmoins, nous établissons dans cette thèse plusieurs familles de facettes. Nous caractérisons également complètement le groupe des automorphismes du polytope ainsi que l'adjacence des sommets du polytope des m-sous-espaces. Un tangle est un ensemble d'hyperplans d'un espace affin contenant un hyperplan par classe d'hyperplans parallèles. Anglada et Maurras ont montré que les tangles définissent des facettes du polytope des hyperplans et que toutes les facettes de ce polytope proviennent de tangles. Nous tentons d'établir une généralisation de ce résultat. Nous élaborons une classification des tangles en familles pour de petites dimensions d'espaces affins. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished