This thesis is concerned with an investigation of the generalizations of continuous real functions of a real variable. In particular, the relationship between uniform continuity and ordinary continuity is concerned. The concept of uniform continuity was first introduced by Heine about 1900.

Philosophiae Doctor - PhD / Understanding the geometries of points in space has been attractive to mathematicians for ages. As a model, twelve years ago, Kurz and Meyer [32] considered point sets in the m-dimensional a ne space Fmq over a nite eld Fq with q = pr elements, p prime, where each squared Euclidean distance of two points is a square in Fq: The latter points are said to be at integral distance in Fmq , and the sets above are called integral point sets.

This paper is concerned with certain properties of derivatives and some characterizations of linear point sets with derivatives. In 1946, Zygmunt Zahorski published a letter on this topic listing a number of theorems without proof, and no proof of these assertions has been published. Some of the theorems presented here are paraphrases of Zahorski's statements, developed in a slightly different order.

Let M be a finite set of random uniformly distributed points lying in a unit cube. Every four points from M make a tetrahedron and the tetrahedron can either contain some of the other points from M, or it can be empty. This diploma thesis brings an upper bound of the expected value of the number of empty tetrahedra with respect to size of M. We also show how precise is the upper bound in comparison to an approximation computed by a straightforward algorithm. In the last section we move from the three- dimensional case to a general dimension d. In the general d-dimensional case we have empty d-simplices in a d-hypercube instead of empty tetrahedra in a cube. Then we compare the upper bound for d-dimensional case to the results from another paper on this topic. 1

Importance sampling is a well known variance reduction technique for Monte Carlo simulation. For quasi-Monte Carlo integration with low discrepancy sequences it was neglected in the literature although it is easy to see that it can reduce the variation of the integrand for many important integration problems. For lattice rules importance sampling is of highest importance as it can be used to obtain a smooth periodic integrand. Thus the convergence of the integration procedure is accelerated. This can clearly speed up QMC algorithms for integration problems up to dimensions 10 to 12. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Let fd(n), n > d ≥ 2, be the smallest positive integer such that any set of fd(n) points, in general position in Rd , contains n points in convex position. Let hd(n, k), n > d ≥ 2 and k ≥ 0, denote the smallest number with the property that in any set of hd(n, k) points, in general position in Rd , there are n points in convex position whose convex hull contains at most k other points. Previous result of Valtr states that h4(n, 0) does not exist for all n ≥ 249. We show that h4(n, 0) does not exist for all n ≥ 137. We show that h3(8, k) ≤ f3(8) for all k ≥ 26, h4(10, k) ≤ f4(10) for all k ≥ 147 and h5(12, k) ≤ f5(12) for all k ≥ 999. Next, let fd(k, n) be the smallest number such that in every set of fd(k, n) points, in general position in Rd , there are n points whose convex hull has at least k vertices. We show that, for arbitrary integers n ≥ k ≥ d + 1, d ≥ 2, fd(k, n) ≥ (n − 1) (k − 1)/(cd logd−2 (n − 1)) , where cd > 0 is a constant dependent only on the dimension d. 1

In many machine learning problems and application domains, the data are naturally organized by groups. For example, a video sequence is a group of images, an image is a group of patches, a document is a group of paragraphs/words, and a community is a group of people. We call them the collective data. In this thesis, we study how and what we can learn from collective data. Usually, machine learning focuses on individual objects, each of which is described by a feature vector and studied as a point in some metric space. When approaching collective data, researchers often reduce the groups into vectors to which traditional methods can be applied. We, on the other hand, will try to develop machine learning methods that respect the collective nature of data and learn from them directly. Several different approaches were taken to address this learning problem. When the groups consist of unordered discrete data points, it can naturally be characterized by its sufficient statistics – the histogram. For this case we develop efficient methods to address the outliers and temporal effects in the data based on matrix and tensor factorization methods. To learn from groups that contain multi-dimensional real-valued vectors, we develop both generative methods based on hierarchical probabilistic models and discriminative methods using group kernels based on new divergence estimators. With these tools, we can accomplish various tasks such as classification, regression, clustering, anomaly detection, and dimensionality reduction on collective data. We further consider the practical side of the divergence based algorithms. To reduce their time and space requirements, we evaluate and find methods that can effectively reduce the size of the groups with little impact on the accuracy. We also proposed the conditional divergence along with an efficient estimator in order to correct the sampling biases that might be present in the data. Finally, we develop methods to learn in cases where some divergences are missing, caused by either insufficient computational resources or extreme sampling biases. In addition to designing new learning methods, we will use them to help the scientific discovery process. In our collaboration with astronomers and physicists, we see that the new techniques can indeed help scientists make the best of data.

No description available.

This thesis addresses the problem of registering one point set with respect to another. This problem arises in the context of the use of CMM/Scanners to inspect objects especially with freeform surfaces. The tolerance verification process now requires the comparison of measured points with the nominal geometry. This entails placement of the measured point set in the same reference frame as the nominal model. This problem is referred to as the registration or localization problem. In the most general form the tolerance verification task involves registering multiple point sets corresponding to multi-step scan of an object with respect to the nominal CAD model. This problem is addressed in three phases. This thesis presents a novel approach to automated inspection by matching point sets based on the Iterative Closest Point (ICP) algorithm. The Modified ICP (MICP) algorithm presented in the thesis improves upon the existing methods through the use of a localized region based triangulation technique to obtain correspondences for all the inspection points and achieves dramatic reduction in computational effort. The use of point sets to represent the nominal surface and shapes enables handling different systems and formats. Next, the thesis addresses the important problem of establishing registration between point sets in different reference frames when the initial relative pose between them is significantly large. A novel initial pose invariant methodology has been developed. Finally, the above approach is extended to registration of multiview inspection data sets based on acquisition of transformation information of each inspection view using the virtual gauging concept. This thesis describes implementation to address each of these problems in the area of automated registration and verification leading towards automatic inspection.

This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These are graph parameters dealing with geomet-ric representations of graphs in higher dimensions. Both these parameters are known to be NP-Hard to compute in general and are even hard to approximate within an O(n1− ) factor for any > 0, under standard complexity theoretic assumptions. We studied algorithmic questions for these problems, for certain graph classes, to yield efficient algorithms or approximations. Our results include a polynomial time constant factor approximation algorithm for computing the cubicity of trees and a polynomial time constant (≤ 2.5) factor approximation algorithm for computing the boxicity of circular arc graphs. As far as we know, there were no constant factor approximation algorithms known previously, for computing boxicity or cubicity of any well known graph class for which the respective parameter value is unbounded. We also obtained parameterized approximation algorithms for boxicity with various edit distance parameters. An o(n) factor approximation algorithm for computing the boxicity and cubicity of general graphs also evolved as an interesting corollary of one of these parameterized algorithms. This seems to be the first sub-linear factor approximation algorithm known for computing the boxicity and cubicity of general graphs. Planar grid-drawings of outerplanar graphs: A graph is outerplanar, if it has a planar embedding with all its vertices lying on the outer face. We give an efficient algorithm to 2-vertex-connect any connected outerplanar graph G by adding more edges to it, in order to obtain a supergraph of G such that the resultant graph is still outerplanar and its pathwidth is within a constant times the pathwidth of G. This algorithm leads to a constant factor approximation algorithm for computing minimum height planar straight line grid-drawings of outerplanar graphs, extending the existing algorithm known for 2-vertex connected outerplanar graphs. n−1 3 Maximum matchings in triangle distance Delaunay graphs: Delau-nay graphs of point sets are well studied in Computational Geometry. Instead of the Euclidean metric, if the Delaunay graph is defined with respect to the convex distance function defined by an equilateral triangle, it is called a Trian-gle Distance Delaunay graph. TD-Delaunay graphs are known to be equivalent to geometric spanners called half-Θ6 graphs. It is known that classical Delaunay graphs of point sets always contain a near perfect matching, for non-degenerate point sets. We show that Triangle Distance Delaunay graphs of a set of n points in general position will always l m contain a matching of size and this bound is tight. We also show that Θ6 graphs, a class of supergraphs of half-Θ6 graphs, can have at most 5n − 11 edges, for point sets in general position. Heterochromatic Paths in Edge Colored Graphs: Conditions on the coloring to guarantee the existence of long heterochromatic paths in edge col-ored graphs is a well explored problem in literature. The objective here is to obtain a good lower bound for λ(G) - the length of a maximum heterochro-matic path in an edge-colored graph G, in terms of ϑ(G) - the minimum color degree of G under the given coloring. There are graph families for which λ(G) = ϑ(G) − 1 under certain colorings, and it is conjectured that ϑ(G) − 1 is a tight lower bound for λ(G). We show that if G has girth is at least 4 log2(ϑ(G))+2, then λ(G) ≥ ϑ(G)− 2. It is also proved that a weaker requirement that G just does not contain four-cycles is enough to guarantee that λ(G) is at least ϑ(G) −o(ϑ(G)). Other special cases considered include lower bounds for λ(G) in edge colored bipartite graphs, triangle-free graphs and graphs without heterochromatic triangles.