42 Result(s)
within
Chapter
Stephane Durocher
Algorithm Analysis and Problem Complexity
-
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
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...
-
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
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...
