21 Result(s)
within
Chapter
Conference Paper
Stephane Durocher
Algorithm Analysis and Problem Complexity
Data Structures
-
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
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
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
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
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...
-
Chapter and Conference Paper
Thickness and Colorability of Geometric Graphs
The geometric thickness \(\bar\theta\) (G) of a graph G is the smallest integer t such that there exist a straight-line drawing Γ ...
-
Chapter and Conference Paper
Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees
We present O(n)-space data structures to support various range frequency queries on a given array A[0:n − 1] or tree T with n nodes. Given a query consisting of an arbitrary pair of pre-order rank indices (i,j), ...
-
Chapter and Conference Paper
Guarding Orthogonal Art Galleries Using Sliding Cameras: Algorithmic and Hardness Results
Let P be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment s ⊆ P as its trajectory. The camera can see a point p ∈ P if there exists a point q ∈ s such ...
-
Chapter and Conference Paper
Revisiting the Problem of Searching on a Line
We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. Prior to ...
-
Chapter and Conference Paper
Plane 3-trees: Embeddability and Approximation
We give an O(nlog3 n)-time linear-space algorithm that, given a plane 3-tree G with n vertices and a set S of n points in the plane, determines whether G has a point-set embedding on S (i.e., a plan...
-
Chapter and Conference Paper
Linear-Space Data Structures for Range Minority Query in Arrays
We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α fraction of the elements ...
-
Chapter and Conference Paper
Robust Nonparametric Data Approximation of Point Sets via Data Reduction
In this paper we present a novel nonparametric method for simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. We consid...
-
Chapter and Conference Paper
Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position
Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is c...
-
Chapter and Conference Paper
Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order
A binary string B of length n = k t is a k-ary Dyck word if it contains t copies of 1, and the number of 0s in every prefix of B is at most k−1 times the number of 1s. We provide two loopless algori...
-
Chapter and Conference Paper
Faster Optimal Algorithms for Segment Minimization with Small Maximal Value
The segment minimization problem consists of finding the smallest set of integer matrices (segments) that sum to a given intensity matrix, such that each summand has only one non-zero value (the segment-value), a...
-
Chapter and Conference Paper
Reconstructing Polygons from Scanner Data
A range-finding scanner can collect information about the shape of an (unknown) polygonal room in which it is placed. Suppose that a set of scanners returns not only a set of points, but also additional inform...
-
Chapter and Conference Paper
Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
Given m unit disks and n points in the plane, the discrete unit disk cover problem is to select a minimum subset of the disks to cover the points. This problem is NP-hard [11] and the best previous practical solu...
-
Chapter and Conference Paper
Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance
Given a simple polygon P, we consider the problem of finding a convex polygon Q contained in P that minimizes H(P,Q), where H denotes the Hausdorff distance. We call such a polygon Q a Hausdorff core of P. We des...
