Combinatorial and geometric problems on point processes

In this dissertation we study three random structures derived from point processes.; We study the circumscribed random polytope Pn of a convex set K ⊂ Rd with smooth boundary, defined to be the intersection of n randomly chosen supporting half-spaces to K with boundary tangent to ∂K. Using cap covering techniques developed by Barany and Larman [13] and sharp concentration arguments developed by R. et al. [87] we demonstrate that the excess volume Vold(PnK) is sharply concentrated about its mean, give an asymptotic characterization for the variance, and demonstrate that a Poissonized variant obeys a central limit theorem.; We introduce a random tree model with vertices in a convex set K ⊂ Rd and designated point o ∈ K, based on a related model of Fabrikant et al. [48]. Vertices vi are chosen uniformly at random and added sequentially via a single edge to the prior vertex vj which minimizes the function: avi-vj +vj -o. We classify edges as local or global by comparison with the cord ovi , and analyze the number of local (global, respectively) edges based on the parameter alpha.; Finally, we introduce a new random graph model based on the random-connection model of continuum percolation [73]. The vertices are given by a point process and the probability that any two vertices forms an edge is given by some non-increasing function rho of the distance between them. We focus primarily on the Riemannian manifold case and functions rho with polynomial tails. Based on the manifold and rho, we give explicit formulae for the probability that two points are connected by an edge, and determine the connectivity threshold for the graph. We additionally examine the geometric scaling of the graph on the cube [0,1]d by looking at induced subgraphs in sub-cubes of length epsilon.