484 research outputs found
Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching
No full textWe describe a general probabilistic framework to address a variety of Fréchet-distance optimization problems. Specifically, we are interested in finding minimal bottleneck-paths in d-dimensional Euclidean space between given start and goal points, namely paths that minimize the maximal value over a continuous cost map. We present an efficient and simple sampling-based framework for this problem, which is inspired by, and draws ideas from, techniques for robot motion planning. We extend the framework to handle not only standard bottleneck pathfinding, but also the more demanding case, where the path needs to be monotone in all dimensions. Finally, we provide experimental results of the framework on several types of problems
Throwing a Sofa Through the Window
No full textWe study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically:
ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}).
iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too.
iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W.
v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time.
vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed.
vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂.
viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴)
Improved implementation of controlled perturbation for arrangements of spheres
No full textWe describe modifications to the implementation of the perturbation scheme for arrangements of spheres presented by Halperin and Shelton [6], which they applied to computing molecular surfaces. The most significant change is allowing a di#erent direction for the "trapezoidal" decomposition on each sphere. Our modifications significantly improved the running time of the construction of the surfaces of large molecules
Multi-Robot Motion Planning for Unit Discs with Revolving Areas
No full textWe study the problem of motion planning for a collection of labeled unit
disc robots in a polygonal environment. We assume that the robots have
revolving areas around their start and final positions: that each start and
each final is contained in a radius disc lying in the free space, not
necessarily concentric with the start or final position, which is free from
other start or final positions. This assumption allows a weakly-monotone motion
plan, in which robots move according to an ordering as follows: during the turn
of a robot in the ordering, it moves fully from its start to final
position, while other robots do not leave their revolving areas. As passes
through a revolving area, a robot that is inside this area may move within
the revolving area to avoid a collision. Notwithstanding the existence of a
motion plan, we show that minimizing the total traveled distance in this
setting, specifically even when the motion plan is restricted to be
weakly-monotone, is APX-hard, ruling out any polynomial-time
-approximation algorithm.
On the positive side, we present the first constant-factor approximation
algorithm for computing a feasible weakly-monotone motion plan. The total
distance traveled by the robots is within an factor of that of the
optimal motion plan, which need not be weakly monotone. Our algorithm extends
to an online setting in which the polygonal environment is fixed but the
initial and final positions of robots are specified in an online manner.
Finally, we observe that the overhead in the overall cost that we add while
editing the paths to avoid robot-robot collision can vary significantly
depending on the ordering we chose. Finding the best ordering in this respect
is known to be NP-hard, and we provide a polynomial time -approximation algorithm for this problem
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
No full textWe present efficient dynamic data structures for maintaining the union of
unit discs and the lower envelope of pseudo-lines in the plane. More precisely,
we present three main results in this paper:
(i) We present a linear-size data structure to maintain the union of a set of
unit discs under insertions. It can insert a disc and update the union in
time, where is the current number of unit discs and
is the combinatorial complexity of the structural change in the union due to
the insertion of the new disc. It can also compute, within the same time bound,
the area of the union after the insertion of each disc.
(ii) We propose a linear-size data structure for maintaining the lower
envelope of a set of -monotone pseudo-lines. It can handle
insertion/deletion of a pseudo-line in time; for a query point
, it can report, in time, the point on the lower
envelope with -coordinate ; and for a query point ,
it can return all pseudo-lines lying below in time .
(iii) We present a linear-size data structure for storing a set of circular
arcs of unit radius (not necessarily on the boundary of the union of the
corresponding discs), so that for a query unit disc , all input arcs
intersecting can be reported in time, where
is the output size and is an arbitrarily small constant.
A unit-circle arc can be inserted or deleted in time.Comment: 29 pages, 19 figures; this article is an extension of our previous
work arXiv:1902.09565; a preliminary version appeared at SoCG 201
shuman_online_appendix – Supplemental material for Threat to the Group’s Image Can Motivate High Identifiers to Take Action Against In-group Transgressions
No full textSupplemental material, shuman_online_appendix for Threat to the Group’s Image Can Motivate High Identifiers to Take Action Against In-group Transgressions by Eric Shuman, Dan Johnson, Tamar Saguy and Eran Halperin in Personality and Social Psychology Bulletin</p
A Near-Quadratic Algorithm for Planning the Motion of a Polygon in a Polygonal Environment
No full textWe consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We present an algorithm that constructs a single component of the free configuration space of B in time O((kn) 2+" ), for any " ? 0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion planning problem, within the same running time. 1 Introduction Let B be an arbitrary polygonal object with k sides, and let V be an open planar polygonal region bounded by n edges. The configuration space C of B is a 3dimensional parametric space, each point of which represents a possible placement of B by the parameterization (x; y; `), where (x; y) are the coordinates of some fixed Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Gran..
National Poetry Month Readings: Local Poets (Audio)
No full textDuring April 2015, in celebration of National Poetry Month, the James E. Brooks Library hosted a series of poetry readings featuring local poets. The readings were held in the library’s first floor Academic & Research Commons. The series was arranged and the readings were introduced by Gerard Hogan, Instruction Librarian at the Brooks Library.
On Thursday, April 30th, Mark Halperin and Keely Murphy Pickerel were the featured poets. Streaming audio of the program is available through Soundcloud here, or by clicking the link above.
Mark Halperin’s most recent poems appear in his chap book, Time After Time (D-Press, 2015). His fifth volume of poetry, Falling Through the Music, was published by University of Notre Dame Press (2007). Halperin is also the co-author of Accent on Meter (NCTE), and co-translator of A Million Premonitions, poems from the Russian of Viktor Sosnora (Zephyr Press). A retired professor of English at CWU, he has published numerous articles related to fly fishing and lives near the Yakima River with his wife, the artist Bobbie Halperin, and their dog, Aimee.
Keely Murphy Pickerel is a poet that lives with her family in Dog Town of Ellensburg, Washington. She earned her degree at CWU in Professional & Creative Writing. Her chapbook, This Steady Place, was published by Blue Begonia Press (2005)
- …
