20 Result(s)
-
Chapter and Conference Paper
Minimum Ply Covering of Points with Unit Squares
Given a set P of points and a set U of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of P with U is a subset of U that covers P and minimizes the number of squares that share a common int...
-
Chapter and Conference Paper
Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon
We consider the problem of finding a geodesic disc of smallest radius containing at least k points from a set of n points in a simple polygon that has m vertices, r of which are reflex vertices. We refer to such ...
-
Chapter and Conference Paper
Computing the k-Crossing Visibility Region of a Point in a Polygon
Two points p and q in a simple polygon P are k-crossing visible when the line segment pq crosses the boundary of P at most k times. Given a query point q, an integer k, and a polygon P, we propose an algorithm th...
-
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
Drawing Graphs Using Body Gestures
We introduce a new gesture-based user interface for drawing graphs that recognizes specific body gestures using the Microsoft Kinect sensor. Our preliminary user study demonstrates the potential for using gest...
-
Chapter and Conference Paper
Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
We wish to decide whether a simply connected flexible polygonal structure can be realized in Euclidean space. Two models are considered: polygonal linkages (body-and-joint framework) and contact graphs of unit...
-
Chapter and Conference Paper
Trade-Offs in Planar Polyline Drawings
Angular resolution, area and the number of bends are some important aesthetic criteria of a polyline drawing. Although trade-offs among these criteria have been examined over the past decades, many of these tr...
-
Chapter and Conference Paper
Drawing Planar Graphs with Reduced Height
A straight-line (respectively, polyline) drawing Γ of a planar graph G on a set L k of k parallel lines is a planar drawing that maps each vertex of G to a dist...
-
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
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
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
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 ...
