Source author record

Thomas C. Shermer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An Efficient Algorithm for the Proximity Connected Two Center Problem

Given a set $P$ of $n$ points in the plane, the $k$ -center problem is to find $k$ congruent disks of minimum possible radius such that their union covers all the points in $P$ . The $2$ -center problem is a special case of the $k$ -center problem that has been extensively studied in the recent past \cite{CAHN,HT,SH}. In this paper, we consider a generalized version of the $2$ -center problem called \textit{proximity connected} $2$ -center (PCTC) problem. In this problem, we are also given a parameter $δ\geq 0$ and we have the additional constraint that the distance between the centers of the disks should be at most $δ$ . Note that when $δ=0$ , the PCTC problem is reduced to the $1$ -center(minimum enclosing disk) problem and when $δ$ tends to infinity, it is reduced to the $2$ -center problem. The PCTC problem first appeared in the context of wireless networks in 1992 \cite{ACN0}, but obtaining a nontrivial deterministic algorithm for the problem remained open. In this paper, we resolve this open problem by providing a deterministic $O(n^2\log n)$ time algorithm for the problem.

preprint2015arXiv

A Combinatorial Bound for Beacon-based Routing in Orthogonal Polygons

Beacon attraction is a movement system whereby a robot (modeled as a point in 2D) moves in a free space so as to always locally minimize its Euclidean distance to an activated beacon (which is also a point). This results in the robot moving directly towards the beacon when it can, and otherwise sliding along the edge of an obstacle. When a robot can reach the activated beacon by this method, we say that the beacon attracts the robot. A beacon routing from $p$ to $q$ is a sequence $b_1, b_2,$ ..., $b_{k}$ of beacons such that activating the beacons in order will attract a robot from $p$ to $b_1$ to $b_2$ ... to $b_{k}$ to $q$ , where $q$ is considered to be a beacon. A routing set of beacons is a set $B$ of beacons such that any two points $p, q$ in the free space have a beacon routing with the intermediate beacons $b_1, b_2,$ ..., $b_{k}$ all chosen from $B$ . Here we address the question of "how large must such a $B$ be?" in orthogonal polygons, and show that the answer is "sometimes as large as $[(n-4)/3]$ , but never larger."

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.