Sep 2026· Modelling and Data Analysis· 0 citations· 4 references
TL;DR
The algorithm enumerating the set of feasible routes showed a significant advantage over simple -fold enumeration of the elements of the elements of .
Abstract
Context and relevance. There are practically significant problems requiring connecting two given points in a plane with a piecewise rectilinear polyline. Various constraints on the desired polyline are possible, including a limit on the number of links n and on the absolute value of the rotation angles at the breakpoints. In the simplest discrete case, the turning points belong to a finite set containing N elements. A complete enumeration of all possible solutions is an NP-hard problem and may require searching through variants. However, approaches are possible that significantly narrow the set of feasible solutions. One such approach is to use an exact formula describing the set of all polylines (described as a sequence of n turning points) that satisfy a given constraint on the absolute value of the rotation angles. In this case, the feasible domain is successively significantly narrowed for each subsequent rotation. As a result, an algorithm for enumerating the elements of precisely such a set will perform many times faster than an exhaustive search algorithm. Objective. Implement an algorithm for enumerating a set of feasible solutions according to a precise formula. Hypothesis. To implement an algorithm that enumerates the set of feasible solutions according to the exact formula. Methods and materials. The software package that implements the search algorithm was developed to work with images representing a route complexity map. After setting the angle constraint and specifying the required number of turns, the package applies an enumeration algorithm over the set of feasible solutions using the exact formula obtained by dynamic programming. Results. Experiments were conducted on four maps with the number of turns equal to 2, 3, and 4. The algorithm enumerating the set of feasible routes showed a significant advantage over simple -fold enumeration of the elements of . A cubic dependence of the algorithm’s running time on the maximum turning angle was experimentally established. Conclusions. The developed algorithm is many times faster than simple enumeration and allows solving a large number of problems in an acceptable time.
A peeling sequence of a finite planar point set is an ordering of its points, such that when the points get removed in this order, each removed point is a vertex of the current convex hull of the set. Write $g(S)$ for the number of such sequences, and $g(n)$ for the minimum of $g(S)$ over $n$-point sets in general posi...
A ship starts at a point of the plane and moves at unit speed; it has to reach an unknown straight line, of which neither the distance nor the direction is known. The competitive ratio of a path is the supremum, over all lines, of the time at which the line is reached divided by its distance. Baeza-Yates, Culberson and...
We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity...
A self-similar reduction theorem is established for homogeneous search problems whose historical information is a record profile updated by pointwise maximum and the optimal deterministic planar Shoreline value $C_2^*$ is a computable real.
Exact forward triangle listers orient each edge of a graph by a vertex order. The order does not change the output, but it changes the work. For the adaptive lister, which scans the smaller of the two forward neighborhoods, the number of candidate tests is a known sum of minima of forward degrees, but how to optimize i...
Introduction
. The problem of determining the principal directions of a point set in the plane or in space is solved numerically. The task is to determine the orientation of an extremal line passing through the centroid of the set and minimizing or maximizing the functional defined as the sum of the squared dist...
N. К. Volosova, K. A. Volosov, A. K. Volosova et al.· COMPUTATIONAL MATHEMATICS AN...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.