Home
Resource
Some results in computational and combinatorial geometry
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(876.91 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Shabbir, Mudassir. Some results in computational and combinatorial geometry. Retrieved from https://doi.org/doi:10.7282/T32Z174F

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleSome results in computational and combinatorial geometry
NameShabbir, Mudassir (author); Steiger, William (chair); Kahn, Jeffry (internal member); Szegedy, Mario (internal member); Aronov, Boris (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2014
Other Date2014-10 (degree)
SubjectComputer Science, Discrete geometry, Computational geometry
Extent1 online resource (viii, 105 p. : ill.)
DescriptionIn 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.
NotePh.D.
NoteIncludes bibliographical references
Noteby Mudassir Shabbir
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T32Z174F
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024