47 Result(s)
within
Chapter
Stephane Durocher
-
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
Top-k Color Queries on Tree Paths
We present a data structure for the following problem: Given a tree \(\mathcal{T}\) , with each of its nodes assigned a color in a...
-
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
On Balanced -Contact Representations
In a -contact representation of a planar graph G, each vertex is represented as an axis-aligned plus shape consisting of two intersectin...
-
Chapter and Conference Paper
On Graphs That Are Not PCGs
Let T be an edge weighted tree and let d min ,d max be two nonnegative real numbers. Then the pairwise compat...
-
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
A Simple Linear-Space Data Structure for Constant-Time Range Minimum Query
We revisit the range minimum query problem and present a new O(n)-space data structure that supports queries in O(1) time. Although previous data structures exist whose asymptotic bounds match ours, our goal is t...
-
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
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
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
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...
