14 Result(s)
within
Chapter
Stephane Durocher
English
Algorithm Analysis and Problem Complexity
Numeric Computing
-
Chapter and Conference Paper
Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon
We study the problem of computing the k-visibility region in the memory-constrained model. In this model, the input resides in a randomly accessible read-only memory of O(n) words, with
-
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
Guarding Monotone Art Galleries with Sliding Cameras in Linear Time
A sliding camera in an orthogonal polygon \(P\) is a point guard
-
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
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
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
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
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
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
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 ...
