Source author record

Matt Gibson

Matt Gibson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

What is connected

4works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

A Characterization of Consistent Digital Line Segments in Two Dimensions

Our concern is the digitalization of line segments in two dimensions as considered by Chun et al.[Discrete Comput. Geom., 2009] and Christ et al.[Discrete Comput. Geom., 2012]. The key property that differentiates the research of Chun et al. and Christ et al. from other research in digital line segment construction is that the intersection of any two segments must be connected. Such a system of segments is called a consistent digital line segments system (CDS). Chun et al. give a construction for all segments in higher dimensions that share a common endpoint (called consistent digital rays (CDR)) that has asymptotically optimal Hausdorff distance, and Christ et al. give a complete CDS in two dimensions with optimal Hausdorff distance. Christ et al. also give a characterization of CDRs in two dimensions, and they leave open the question on how to characterize CDSes in two dimensions. In this paper, we answer the most important open question regarding CDSes in two dimensions by giving the characterization asked for by Christ et al. We obtain the characterization by giving a set of necessary and sufficient conditions that a CDS must satisfy.

preprint2015arXiv

A Characterization of Visibility Graphs for Pseudo-Polygons

In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to a characterization of vertex-edge visibility graphs given by O'Rourke and Streinu.

preprint2011arXiv

On Isolating Points Using Disks

In this paper, we consider the problem of choosing disks (that we can think of as corresponding to wireless sensors) so that given a set of input points in the plane, there exists no path between any pair of these points that is not intercepted by some disk. We try to achieve this separation using a minimum number of a given set of unit disks. We show that a constant factor approximation to this problem can be found in polynomial time using a greedy algorithm. To the best of our knowledge we are the first to study this optimization problem.

preprint2010arXiv

Approximation Algorithms for Dominating Set in Disk Graphs

We consider the problem of finding a lowest cost dominating set in a given disk graph containing $n$ disks. The problem has been extensively studied on subclasses of disk graphs, yet the best known approximation for disk graphs has remained $O(\log n)$ -- a bound that is asymptotically no better than the general case. We improve the status quo in two ways: for the unweighted case, we show how to obtain a PTAS using the framework recently proposed (independently)by Mustafa and Ray [SoCG 09] and by Chan and Har-Peled [SoCG 09]; for the weighted case where each input disk has an associated rational weight with the objective of finding a minimum cost dominating set, we give a randomized algorithm that obtains a dominating set whose weight is within a factor $2^{O(\log^* n)}$ of a minimum cost solution, with high probability -- the technique follows the framework proposed recently by Varadarajan [STOC 10].