We address the problem of designing a distributed algorithm for two robots that sketches the boundary of an unknown shape. Critically, we assume a certain amount of delay in how quickly our robots ...can react to external feedback. In particular, when a robot moves, it commits to move along path of length at least λ, or turn an amount of radians at least λ for some positive λ≤1/26, that is normalized based on a unit diameter shape. Then, our algorithm outputs a polygon that is an ϵ-sketch, for ϵ=8λ, in the sense that every point on the shape boundary is within distance ϵ of the output polygon. Moreover, our costs are asymptotically optimal in two key criteria for the robots: total distance traveled and total amount of rotation.
Additionally, we implement our algorithm, and illustrate its output on some specific shapes.
A high-coverage algorithm termed enhanced camera assisted received signal strength ratio (eCA-RSSR) positioning algorithm is proposed for visible light positioning (VLP) systems. The basic idea of ...eCA-RSSR is to utilize visual information captured by the camera to estimate first the incidence angles of visible lights. Based on the incidence angles, eCA-RSSR utilizes the received signal strength ratio (RSSR) calculated by the photodiode (PD) to estimate the ratios of the distances between the LEDs and the receiver. Based on an Euclidean plane geometry theorem, eCA-RSSR transforms the ratios of the distances into the absolute values. In this way, eCA-RSSR only requires three LEDs for both orientation-free 2D and 3D positioning, implying that eCA-RSSR can achieve high coverage. Based on the absolute values of the distances, the linear least square method is employed to estimate the position of the receiver. Therefore, for the receiver having a small distance between the PD and the camera, the accuracy of eCA-RSSR does not depend on the starting values of the non-linear least square method and the complexity of eCA-RSSR is low. Furthermore, since the distance between the PD and camera can significantly affect the performance of eCA-RSSR, we further propose a compensation algorithm for eCA-RSSR based on the single-view geometry. Experiment results show that positioning errors of less than five centimeters is achievable for eCA-RSSR. Simulation results show that eCA-RSSR can achieve 80th percentile accuracy of about four centimeters and can improve the coverage ratio at low cost.
We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set of n pairs of points (terminals) ...T={{ti,ti′}}i=1n in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that ti and ti′ belong to a same cycle, for each i∈{1,…,n}. This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations.
In Korchmáros et al. (2018)one-factorizations of the complete graph Kn are constructed for n=q+1 with any odd prime power q such that either q≡1(mod4) or q=2h−1. The arithmetic restriction n=q+1 is ...due to the fact that the vertices of Kn in the construction are the points of a conic Ω in the finite plane of order q. Here we work on the Euclidean plane and describe an analogous construction where the role of Ω is taken by a regular n-gon. This allows us to remove the above constraints and construct one-factorizations of Kn for every even n≥6.
Due to the importance of Hessian structures we express some algebraic and geo\-me\-tric features of two such semi-Riemannian metrics in dimension two. For this purpose we use the separable coordinate ...systems of the Euclidean plane. Several properties are expressed with the Pauli matrices and their associated quadratic forms.
A pedal curve (a contrapedal curve) of a regular plane curve is the locus of the feet of the perpendiculars from a point to the tangents (normals) to the curve. These curves can be parametrized by ...using the Frenet frame of the curve. Yet provided that the curve has some singular points, the Frenet frame at these singular points is not well‐defined. Thus, we cannot use the Frenet frame to examine pedal or contrapedal curves. In this paper, pedal and contrapedal curves of plane curves, which have singular points, are investigated. By using the Legendrian Frenet frame along a front, the pedal and contrapedal curves of a front are introduced and properties of these curves are given. Then, the condition for a pedal (and a contrapedal) curve of a front to be a frontal is obtained. Furthermore, by considering the definitions of the evolute, the involute, and the offset of a front, some relationships are given. Finally, some illustrated examples are presented.
A graph
is minimal non-unit-distance graph if there is no drawing of
in Euclidean plane having all edges of unit length, but, for each edge
of
,
−
has such a drawing. We prove that, for infinitely ...many
, the number of non-isomorphic
-vertex minimal non-unit-distance graphs is at least exponential in
In this paper some new geometric characterizations are given of the following algebraic properties of the underlying field
K
of an Euclidean plane
E
:
-
1
is a square in
K
, the group of squares is ...of index 2 in
K
∗
,
K
is Pythagorean, and
K
is Euclidean. In the first part ordinary incidence conditions of lines and circles in
E
are used for this purpose, while in the second these properties are characterized by comparing four betweenness relations introduced in
E
in a natural way.
We study the generalized minimum Manhattan network (GMMN) problem: given a set
P
of pairs of points in the Euclidean plane
R
2
, we are required to find a minimum-length geometric network which ...consists of axis-aligned segments and contains a shortest path in the
L
1
metric (a so-called Manhattan path) for each pair in
P
. This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in
P
, and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach.
PDF
