![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
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
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
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
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 ...