47 Result(s)
within
Chapter
Stephane Durocher
-
Chapter and Conference Paper
Minimum Ply Covering of Points with Unit Squares
Given a set P of points and a set U of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of P with U is a subset of U that covers P and minimizes the number of squares that share a common int...
-
Chapter and Conference Paper
Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon
We consider the problem of finding a geodesic disc of smallest radius containing at least k points from a set of n points in a simple polygon that has m vertices, r of which are reflex vertices. We refer to such ...
-
Chapter and Conference Paper
Cops and Robbers on 1-Planar Graphs
Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of G is the minimum number of cops ...
-
Chapter and Conference Paper
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
Chvátal and Klincsek (1980) gave an \(O(n^3)\) O (
-
Chapter and Conference Paper
On the Restricted 1-Steiner Tree Problem
Given a set P of n points in \(\mathbb {R}^2\) and an input line ...
-
Chapter and Conference Paper
Computing the k-Crossing Visibility Region of a Point in a Polygon
Two points p and q in a simple polygon P are k-crossing visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, an integer k, and a polygon P, we propose an algorithm th...
-
Chapter and Conference Paper
Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon
We study the problem of computing the k-visibility region in the memory-constrained model. In this model, the input resides in a randomly accessible read-only memory of O(n) words, with
-
Chapter and Conference Paper
Polygon Simplification by Minimizing Convex Corners
Let P be a polygon with \(r>0\) reflex vertices and possibly with holes. A subsuming polygon of P is a polygon ...
-
Chapter and Conference Paper
Drawing Graphs Using Body Gestures
We introduce a new gesture-based user interface for drawing graphs that recognizes specific body gestures using the Microsoft Kinect sensor. Our preliminary user study demonstrates the potential for using gest...
-
Chapter and Conference Paper
Local Routing in Convex Subdivisions
In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local ge...
-
Chapter and Conference Paper
A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
A sliding camera travelling along a line segment s in a polygon P can see a point p in P if and only if p lies on a line segment contained in P that intersects s at a right angle. The objective of the minimum sli...
-
Chapter and Conference Paper
Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit...
-
Chapter and Conference Paper
Drawing HV-Restricted Planar Graphs
A strict orthogonal drawing of a graph G = (V, E) in ℝ2 is a drawing of G such that each vertex is mapped to a distinct point and each edge is mapped to a horizontal or vertical line segment. A graph G is HV-rest...
-
Chapter and Conference Paper
Indexed Geometric Jumbled Pattern Matching
We consider how to preprocess n colored points in the plane such that later, given a multiset of colors, we can quickly find an axis-aligned rectangle containing a subset of the points with exactly those colors, ...
-
Chapter and Conference Paper
Trade-Offs in Planar Polyline Drawings
Angular resolution, area and the number of bends are some important aesthetic criteria of a polyline drawing. Although trade-offs among these criteria have been examined over the past decades, many of these tr...
-
Chapter and Conference Paper
Competitive Online Routing on Delaunay Triangulations
The sequence of adjacent nodes (graph walk) visited by a routing algorithm on a graph G between given source and target nodes s and t is a c-competitive route if its length in G is at most c times the length of t...
-
Chapter and Conference Paper
A (7/2)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
Consider a sliding camera that travels back and forth along an orthogonal line segment s inside an orthogonal polygon P with n vertices. The camera can see a point p inside P if and only if there exists a line se...
-
Chapter and Conference Paper
Drawing Planar Graphs with Reduced Height
A straight-line (respectively, polyline) drawing Γ of a planar graph G on a set L k of k parallel lines is a planar drawing that maps each vertex of G to a dist...
-
Chapter and Conference Paper
Guarding Monotone Art Galleries with Sliding Cameras in Linear Time
A sliding camera in an orthogonal polygon \(P\) is a point guard
-
Chapter and Conference Paper
Complexity of Barrier Coverage with Relocatable Sensors in the Plane
We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in...
