22 Result(s)
-
Chapter and Conference Paper
Minimum-Width Double-Slabs and Widest Empty Slabs in High Dimensions
A slab in d-dimensional space \(\mathbb {R}^d\) R ...
-
Article
Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles
We present an algorithm to compute the geodesic \(L_1\) L 1 ...
-
Article
Maximizing Dominance in the Plane and its Applications
Given a set P of n weighted points, a set Q of m points in the plane, and a positive integer k, we consider the optimization problem of finding a subset of Q with at most k points that dominates a subset of P wit...
-
Article
The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest s...
-
Chapter and Conference Paper
Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain
Given a set of open axis-aligned disjoint rectangles in the plane, each of which behaves as both an obstacle and a target, we seek to find shortest obstacle-avoiding rectilinear paths from a query to the neare...
-
Article
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms
Given a read-only memory for input and a write-only stream for output, an s-workspace algorithm, for a positive integer parameter s, is an algorithm using only O(s) words of workspace in addition to the memory fo...
-
Article
Guest Editor’s Foreword
-
Article
A Generalization of the Convex Kakeya Problem
Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kak...
-
Chapter and Conference Paper
Group Nearest Neighbor Queries in the L 1 Plane
Let P be a set of n points in the plane. The k-nearest neighbor (k-NN) query problem is to preprocess P into a data structure that quickly reports k closest points in P for a query point q. This paper addresses a...
-
Article
Aligning Two Convex Figures to Minimize Area or Perimeter
Given two compact convex sets P and Q in the plane, we consider the problem of finding a placement ϕ P of P that minimizes the convex hull of ϕ P∪Q. We study eight ...
-
Article
Casting an Object with a Core
This paper addresses geometric problems in manufacturing objects by casting. In casting, molten material is poured into the cavity of the cast and allowed to solidify, after which the cast is removed. The cas...
-
Chapter and Conference Paper
Covering a Point Set by Two Disjoint Rectangles
Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In ...
-
Chapter and Conference Paper
Covering a Simple Polygon by Monotone Directions
In this paper we study the problem of finding a set of k directions for a given simple polygon P, such that for each point p ∈ P there is at least one direction in which the line through p intersects the polygon ...
-
Chapter and Conference Paper
Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations
We consider two non-convex enclosing shapes with the minimum area; the L-shape and the quadrant hull. This paper proposes efficient algorithms computing each of two shapes enclosing a set of points with the minim...
-
Chapter and Conference Paper
Dilation-Optimal Edge Deletion in Polygonal Cycles
Let C be a polygonal cycle on n vertices in the plane. A randomized algorithm is presented which computes in O(n log3 n) expected time, the edge of C whose removal results in a polygonal path of s...
-
Article
Casting with Skewed Ejection Direction
Casting is a manufacturing process in which liquid is poured into a cast (mold) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is remove...
-
Chapter and Conference Paper
Casting an Object with a Core
In casting, molten material is poured into the cavity of the cast and allowed to solidify. The cast has two main parts to be removed in opposite parting directions. To manufacture more complicated objects, the...
-
Chapter and Conference Paper
Stacking and Bundling Two Convex Polygons
Given two compact convex sets C 1 and C 2 in the plane, we consider the problem of finding a placement ϕC 1 of C 1 t...
-
Chapter and Conference Paper
Approximation Algorithms for Inscribing or Circumscribing an Axially Symmetric Polygon to a Convex Polygon
Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S′ that contains P. More...
-
Chapter and Conference Paper
Casting a Polyhedron with Directional Uncertainty
Casting is a manufacturing process in which molten material is poured into a cast (mould), which is opened after the material has solidified. As in all applications of robotics, we have to deal with imperfect ...
