Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userChasing Puppies: Mobile Beacon Routing on Closed Curves
104
0
0.0
(
0
)
Added by
Jeff Erickson
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
rate research
Read More
We extend the notion of a source unfolding of a convex polyhedron P to be based on a closed polygonal curve Q in a particular class rather than based on a point. The class requires that Q lives on a cone to both sides; it includes simple, closed quasigeodesics. Cutting a particular subset of the cut locus of Q (in P) leads to a non-overlapping unfolding of the polyhedron. This gives a new general method to unfold the surface of any convex polyhedron to a simple, planar polygon.
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
Can an infinite-strength magnetic beacon always ``catch an iron ball, when the beacon is a point required to be remain nonstrictly outside a polygon, and the ball is a point always moving instantaneously and maximally toward the beacon subject to staying nonstrictly within the same polygon? Kouhestani and Rappaport [JCDCG 2017] gave an algorithm for determining whether a ball-capturing beacon strategy exists, while conjecturing that such a strategy always exists. We disprove this conjecture by constructing orthogonal and general-position polygons in which the ball and the beacon can never be united.
An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of emph{flow-query} related problems: Given a terrain $Sigma$, represented as a triangulated $xy$-monotone surface with $n$ vertices, a rain distribution $R$ which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results: (i) We present an internal-memory algorithm that preprocesses $Sigma$ into a linear-size data structure that for a (possibly time varying) rain distribution $R$ can return the flow-rate functions of all edges of $Sigma$ in $O(rho k+|phi| log n)$ time, where $rho$ is the number of sinks in $Sigma$, $k$ is the number of times the rain distribution changes, and $|phi|$ is the total complexity of the flow-rate functions that have non-zero values; (ii) We also present an I/O-efficient algorithm for preprocessing $Sigma$ into a linear-size data structure so that for a rain distribution $R$, it can compute the flow-rate function of all edges using $O(text{Sort}(|phi|))$ I/Os and $O(|phi| log |phi|)$ internal computation time. (iii) $Sigma$ can be preprocessed into a linear-size data structure so that for a given rain distribution $R$, the flow-rate function of an edge $(q,r) in Sigma$ under the single-flow direction (SFD) model can be computed more efficiently. (iv) We present an algorithm for computing the two-dimensional channel along which water flows using Mannings equation; a widely used empirical equation that relates the flow-rate of water in an open channel to the geometry of the channel along with the height of water in the channel.
In this paper, we design a greedy routing on networks of mobile agents. In the greedy routing algorithm, every time step a packet in agent $i$ is delivered to the agent $j$ whose distance from the destination is shortest among searched neighbors of agent $i$. Based on the greedy routing, we study the traffic dynamics and traffic-driven epidemic spreading on networks of mobile agents. We find that the transportation capacity of networks and the epidemic threshold increase as the communication radius increases. For moderate moving speed, the transportation capacity of networks is the highest and the epidemic threshold maintains a large value. These results can help controlling the traffic congestion and epidemic spreading on mobile networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
