Search Results

For many cases, Yes (but see Dima's and Brian's answers), by work of Yu. Nesterov, A. Nemirovski, as summarized in their book Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies i …

You might look at the literature on the upper envelope (or equivalently, the lower envelope) of a collection of surfaces in $\mathbb{R}^d$. Such upper envelopes arise in a variety of computational geo …

This new paper "develops efficient algorithms for (self-)repulsion of plane and space curves." "Constraining curves to a surface yields Hilbert-like curves that are smooth and evenly-spaced." Chris Y …

I believe the answer is No, the claim is not true. At least not if my reformulation of the question is correct. What the OP calls dispersion is usually viewed as optimal packing of $n$ congruent circl …

Just an illustration of @RichardKlitzing's construction in 3D:       His $n+1 = 4$ layers are: $$ v_1 \;,\; \{v_2,v_4,v_5\} \;,\; \{v_3,v_8,v_6\} \;,\; v_7 $$

This will be a high-level suggestion, and definitely not optimal. First, execute a sweepline algorithm to detect all the points of intersections between segments and circles. Then for each segment, r …

The answer is Yes: "one can pre-process things with a higher up-front cost so as to make individual queries faster." The Ph.D. thesis cited below shows that, with quadratic preprocessing, point-pair …

This is not an answer and adds little, but ... It maybe easier to consider a surrounding disk rather than a square. I like the OP's idea of a spiral. Concentric circles allow $a>1$ shortcuts:         …

Not an answer, but two related, almost inverse topics suggesting in which areas of mathematics they fall: (1) The Lonely Runners Conjecture. See, e.g., Terry Tao, "Some remarks on the lonely runner c …

Essentially you want to compute the Voronoi diagram of the ellipses. Then the solution you seek is provided by a circle centered on some vertex of the diagram. The work by Karavelas and Yvinec seems …

Just an illustration of the question:         

This is not an answer, just an example to help visualize the polytope for $m=3$, so in $\mathbb{R}^3$. I used $n=6$ and $k=2$, with $a_1$ and $a_2$ marked in blue, and $\{a_3,a_4,a_5,a_6\}$ in red (th …

This is just a bit of data following Gerhard's and Suvrit's observations. This is a graph of the maximum of $S$, $S_{\max}$, when $n=2$, not showing $x_1$ and $x_2$ that achieve the max, but rather t …

This is speculation, not a precise answer, but I wonder if perhaps Minkowski's theorem on the existence of a polytope with prescribed face normals and areas might help? This theorem is described in d …

This is an incomplete answer, but perhaps these key terms and references could help. Your paths are often called angle-restricted paths in the literature, e.g., Fekete and Woeginger's 1997 "Angle-Rest …