BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em minimum vision points problem}. We prove that finding the minimum number of vision points on a shortest watchman route in a simple polygon is APX-Hard. We then extend the proof to the class of rectilinear polygons having at most three dent orientations.
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Ω(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.
We consider the online two-dimensional vector packing problem, showing a lower bound of 11/5 on the competitive ratio of any {\sc AnyFit} strategy for the problem. We provide strategies with competitive ratio max{2,6/(1+3tan(π/4−γ/2))+ε} and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range [π/4−γ/2,π/4+γ/2], for 0≤γ<π/3 and max{5/2,4/(1+2tan(π/4−γ/2))+ε} and logarithmic advice, for any instance where all the input vectors are restricted to have angles in the range [π/4−γ/2,π/4+γ/2], for 0≤γ≤π/3. In addition, we give a 5/2-competitive strategy also using logarithmic advice for the unrestricted vectors case. These results should be contrasted to the currently best competitive strategy, FirstFit, having competitive ratio~27/10.
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location of half guards in 2-guardable polygons is not restricted to extensions, show that the problem is NP-hard in monotone polygons, and present approximation algorithms for spiral and staircase polygons.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.