2,554 research outputs found
Sea Fox
No full textSea Fox sailing boat. The Sea Fox Saga - in mid-1959 a leaking American yacht, the Sea Fox, limped in to Darwin from Singapore. Amongst those on board were a Hollywood actor/magician, a beautiful show-girl from Manila and a fully-mature bad-tempered chimpanzee. The yacht remained for a couple of weeks and then set sail for the eastern states with a mostly, new crew. They ran into trouble in the Arafura Sea and, with the help of the RAAF and Navy, reached Galiwin'ku where the yacht was further damaged in an attempted beaching. Sea Fox was temporarily repaired and brought back to Darwin where she languished for a number of years while attempts were made to sort out squabbles over ownership, debts, etc. She was eventually bulldozed and burnt at Doctor?s Gully and the remains buried. [Records Territory, January 2007, No. 31.]Woodley, Colleen.Date:1959
Fox chase
No full textharmonicasCollected by Merlin Mitchell
Transcribed by Kyle Perrin
Fox Chase
Reel 27
Item 2
Ewell Napier
Hazel Valley, Ark.
March B, 1950
Now I'm going to give you an impersination of an old time fox chase. But
it ends up beirg a rabbit race.
(Middle of music)--That wasn't no rabbit them dogs was after. It happened
to be dad's old sow. Standing out there whal ago and I seen that old fox coming
over there--! thought it was and it happened to be dad's old sow.Funding for digitization provided by the Arkansas Humanities Council and the Happy Hollow Foundation
Approximating the Geometric Edit Distance
No full textEdit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized O(n log^2n) time O(sqrt n)-approximation algorithm. Then, we generalize our result to give a randomized alpha-approximation algorithm for any alpha in [1, sqrt n], running in time O~(n^2/alpha^2). Both algorithms are Monte Carlo and return approximately optimal solutions with high probability
Approximating the (Continuous) Fréchet Distance
No full textWe describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let P and Q be two polygonal chains with n vertices in d-dimensional Euclidean space, and let α ∈ [√n, n]. Our algorithm deterministically finds an O(α)-approximate Fréchet correspondence in time O((n³ / α²) log n). In particular, we get an O(n)-approximation in near-linear O(n log n) time, a vast improvement over the previously best know result, a linear time 2^O(n)-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an O(log n) factor
Computation of Cycle Bases in Surface Embedded Graphs
No full textWe present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs.
While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well
A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread
No full textThe geometric transportation problem takes as input a set of points P in d-dimensional Euclidean space and a supply function μ : P → ℝ. The goal is to find a transportation map, a non-negative assignment τ : P × P → ℝ_{≥ 0} to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., ∑_{r ∈ P} τ(q, r) - ∑_{p ∈ P} τ(p, q) = μ(q) for all points q ∈ P. The goal is to minimize the weighted sum of Euclidean distances for the pairs, ∑_{(p, q) ∈ P × P} τ(p, q) ⋅ ||q - p||₂.
We describe the first algorithm for this problem that returns, with high probability, a (1 + ε)-approximation to the optimal transportation map in O(n poly(1 / ε) polylog n) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of P and the magnitude of its real-valued supplies
Kyle\u27s The girl’s guide to life (Book Review)
No full textKyle, S. (2015). The girl’s guide to life. Carson, CA: RoseKidz. 192 pp. $10.99. ISBN 9781584111498
Holiest minimum-cost paths and flows in surface graphs
No full textFull text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided Link to Article). All others may find the web address for this item in the full item record as "dc.relation.uri" metadata.Let G be an edge-weighted directed graph with n vertices embedded on an orientable surface of genus g. We describe a simple deterministic lexicographic perturbation scheme that guarantees uniqueness of minimum-cost flows and shortest paths in G. The perturbations take O(gn) time to compute. We use our perturbation scheme in a black box manner to derive a deterministic O(n log log n) time algorithm for minimum cut in directed edge-weighted planar graphs and a deterministic O(g² n log n) time proprocessing scheme for the multiple-source shortest paths problem of computing a shortest path oracle for all vertices lying on a common face of a surface embedded graph. The latter result yields faster deterministic near-linear time algorithms for a variety of problems in constant genus surface embedded graphs. Finally, we open the black box in order to generalize a recent linear-time algorithm for multiple-source shortest paths in unweighted undirected planar graphs to work in arbitrary orientable surfaces. Our algorithm runs in O(g² n log g) time in this setting, and it can be used to give improved linear time algorithms for several problems in unweighted undirected surface embedded graphs of constant genus including the computation of minimum cuts, shortest topologically non-trivial cycles, and minimum homology bases.NSF grants CCF-1408763, IIS-1408846, IIS-1447554, CCF-1513816, CCF-1546392, CCF-1527084, and CCF-1535972; by ARO grant W911NF15-1-0408, and by grant 2012/229 from the U.S.-Israel Binational Science Foundation.Erik Jonsson School of Engineering and Computer Scienc
An Efficient Algorithm for Computing High-Quality Paths Amid Polygonal Obstacles
No full textWe study a path-planning problem amid a set O of obstacles in R², in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ε ∈ (0, 1]. Our algorithm computes in time O(n²/ε² log n/ε) a path of total cost at most (1 + ε) times the cost of the optimal path.NSF grants CCF-09- 40671, CCF-10-12254, CCF-11-61359, CCF-15-13816, IIS-14-08846, IIS-14-09003; U.S.-Israel Binational Science Foundation grant 2012/229; Israel Science Foundation grant 1102/11; German-Israeli Foundation grant 1150-82.6/2011.Erik Jonsson School of Engineering and Computer Scienc
Computing the Gromov-Hausdorff Distance for Metric Trees
No full text
The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time
O
(min
n
, √
rn
)-approximation algorithm for computing the GH distance between a pair of metric trees, where
r
is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an
O
(√
n
)-approximation algorithm
1
.
</jats:p
- …
