Text

theses

In this thesis we present some new results in the field of discrete and computational geometry. The techniques and tools developed to achieve these results add to our understanding of important geometric objects like line arrangements, and geometric measures of depth. Given a set $S$ of $n$ points, a {em weak $epsilon$-net} $X$ is a set of points (not necessarily in $S$) such that any convex set, called a range, that contains more than an $epsilon$ fraction of $S$ must meet $X$ for a fixed $eps>0$ . Aronov {em et al.} gave the first bounds on $eps$ when the cardinality of $X$ is a fixed small number in the plane. Later Mustafa and Ray proved that $|X|=2$ can be chosen so that we hit all convex ranges that contain $4n/7$ points of $S$. We describe an $O(nlog^4 n)$ time algorithm to find points $z_1 ot = z_2$, at least one of which must meet any convex set of ``size'' greater than $4n/7$; $z_1$ and $z_2$ comprise a hitting set of size two for such convex ranges. This is the first algorithm for computing the hitting sets of fixed size. Data-depth measures are real valued functions that are defined on the points of $Re^d$ with respect to a given set $S$ in $Re^d$. They are helpful in nonparametric statistical analysis by partitioning the space in a center-outwardly fashion. We introduced a new framework to study many well-known data-depth measures in a uniform way. We define and provide first bounds for {em line-depth} and show how it bridges the relation among Tukey-depth, simplicial-depth, and ray-shooting depth measures in $Re^3$. We also develop the first algorithm to efficiently compute a point of {em high} ray-shooting depth in the plane. Faults and viruses often spread in the networked environments by propagating from a site to neighboring site. We model this process of {em network contamination} by using graphs. Consider a graph $G=(V,E)$, whose vertex set is contaminated. Our goal is to decontaminate the set $V(G)$ using the mobile agents that move along the edge set of $G$. The {em temporal immunity }$au(G) ge 0$ is defined as the time that a decontaminated vertex of $G$ can remain continuously exposed to a contaminated neighbor without getting infected itself. We study the lower and upper bounds on the temporal immunity required to decontaminate some classes of graphs - mostly geometric - that correspond to some well-known network topologies, and we present an upper bounds on $iota_1(G)$, in some cases with matching lower bounds.

ETD_5724

Ph.D.

Includes bibliographical references

by Mudassir Shabbir

doi:10.7282/T32Z174F

ETD doctoral

The author owns the copyright to this work.