Spelling suggestions: "subject:"convex polytope"" "subject:"konvex polytope""
1 
Linear Time Approximation of 3D Convex PolytopesMario A. Lopez, Shlomo Reisner, reisner@math.haifa.ac.il 05 March 2001 (has links)
No description available.

2 
A new algorithm for finding the minimum distance between two convex hullsKaown, Dougsoo. Liu, Jianguo, January 2009 (has links)
Thesis (Ph. D.)University of North Texas, May, 2009. / Title from title page display. Includes bibliographical references.

3 
Polytopal digraphs and nonpolytopal facet graphs /Mihalisin, James Edward. January 2001 (has links)
Thesis (Ph. D.)University of Washington, 2001. / Vita. Includes bibliographical references (p. 6973).

4 
Minkowski sum decompositions of convex polygonsSeater, Robert. January 2002 (has links)
Thesis (B.A.)Haverford College, Dept. of Mathematics, 2002. / Includes bibliographical references.

5 
Minimizing the mass of the codimensiontwo skeleton of a convex, volumeone polyhedral regionJanuary 2011 (has links)
In this paper we establish the existence and partial regularity of a (d2)dimensional edgelength 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 (d2)dimensional edgelength ζ d 2 is lowersemicontinuous 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.

6 
A New Algorithm for Finding the Minimum Distance between Two Convex HullsKaown, Dougsoo 05 1900 (has links)
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.

7 
Hitting Geometric Range Spaces using a Few PointsAshok, Pradeesha January 2014 (has links) (PDF)
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 deﬁned by the intersection of geometric objects with P . The algorithmic question of ﬁnding the minimumsized hitting set for a given range space is well studied and is NPComplete even for geometric range spaces deﬁned by unit disks. The dual of the hitting set problem is the equally well studied set cover problem. A set cover is a subcollection 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 ﬁnd 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 speciﬁc geometric range spaces where the size of the hitting set is ﬁxed as a small constant. We study the small hitting set problem mainly for two broad classes of range spaces.
We ﬁrst consider the Dense range space (P, S) where P is a set of n points in Rd and S is deﬁned by “dense” geometric objects i.e, geometric objects that contain more than a constant fraction, say �, of points from P . We ﬁx 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 deﬁned 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 deﬁned 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 deﬁned by a ﬁxed set of orientations : Geometric range spaces like those induced by axisparallel 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 �Snet 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 axisparallel 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 ﬁrst selection lemma for induced rectangles, induced special rectangles and induced disks. We prove an exact result for the strong variant of the ﬁrst selection lemma for axisparallel rectangles. We also prove exact results for the strong variant of the ﬁrst selection lemma for some subclasses of axisparallel rectangles like orthants and slabs. We prove strong ﬁrst selection lemma with almost tight bounds for skylines, another subclass of axisparallel rectangles. We prove bounds for ﬁrst 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.

8 
Le polytope des sousespaces d'un espace affin fini / Polytope of subspaces of a finite affine spaceChristophe, Jean 29 September 2006 (has links)
Le polytope des msousespaces est défini comme l'enveloppe convexe des vecteurs caractéristiques de tous les sousespaces 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 msousespaces 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 msousespaces. 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:eurepo/semantics/nonPublished

Page generated in 0.0613 seconds