7 Result(s)
within
Chapter
Conference Paper
Stephane Durocher
Algorithm Analysis and Problem Complexity
Algorithms
Data Structures
-
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
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 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
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
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
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...
