47 Result(s)
within
Chapter
Stephane Durocher
-
Chapter and Conference Paper
Kinetic Maintenance of Mobile k-Centres on Trees
Let C denote a set of n mobile clients, each of which follows a continuous trajectory on a weighted tree T. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C. When each ...
-
Chapter and Conference Paper
Balancing Traffic Load Using One-Turn Rectilinear Routing
We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and origin and destination nodes correspond to pairs of points in that region. The objective is...
-
Chapter and Conference Paper
On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks
We study routing algorithms for three-dimensional ad hoc networks that guarantee delivery and are k-local, i.e., each intermediate node v’s routing decision only depends on knowledge of the labels of the source 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...
-
Chapter and Conference Paper
Untangled Monotonic Chains and Adaptive Range Search
We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data with more inherent sorte...
-
Chapter and Conference Paper
On the Structure of Small Motif Recognition Instances
Given a set of sequences, S, and degeneracy parameter, d, the Consensus Sequence problem asks whether there exists a sequence that has Hamming distance at most d from each sequence in S. A valid motif set is a se...
-
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
Range Majority in Constant Time and Linear Space
Given an array A of size n, we consider the problem of answering range majority queries: given a query range [i..j] where 1 ≤ i ≤ j ≤ n, return the majority element of the subarray A[i..j] if it exists. We descri...
-
Chapter and Conference Paper
Hamiltonian Paths and Cycles in Planar Graphs
We examine the problem of counting the number of Hamiltonian paths and Hamiltonian cycles in outerplanar graphs and planar graphs, respectively. We give an O(nα n ) up...
-
Chapter and Conference Paper
Embedding Plane 3-Trees in ℝ2 and ℝ3
A point-set embedding of a planar graph G with n vertices on a set P of n points in ℝ d , d ≥ 1, is a straight-line drawing of G, where the vertices of G are mapped to distinct p...
-
Chapter and Conference Paper
On the Hardness of Point-Set Embeddability
A point-set embedding of a plane graph G with n vertices on a set S of n points is a straight-line drawing of G, where the vertices of G are mapped to distinct points of S. The problem of deciding whether a plane...
-
Chapter and Conference Paper
Computing Partitions of Rectilinear Polygons with Minimum Stabbing Number
The stabbing number of a partition of a rectilinear polygon P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment contained in P. We consider the problem of finding a rec...
-
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
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 Γ ...
