Search Results

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 …

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 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 …

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 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 …

There is a recent paper by John Sullivan entitled "Curvatures of Smooth and Discrete Surfaces" in the collection Discrete Differential Geometry, but available also in an earlier arXiv version. Here i …

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 …

Here is a function $f(x,y)$ which is 0 inside the square $C=[\pm1,\pm1]$, and outside that square has value equal to the Euclidean distance $d( p, C )$ from $p=(x,y)$ to the boundary of $C$. [I am try …

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 …

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 …

There is quite a large literature on shortest paths on polyhedral surfaces, where the distance function is either Euclidean distance or more general metrics. For example, this recent paper extends to …

Two examples, neither a direct hit on what you seek, I think. But maybe they will trigger connections for others to answer better. (1) Moody T. Chu and Matthew M. Lin. "Low-Dimensional Polytope …

The following paper studies this "milling" problem (generalized) from a complexity viewpoint: Arkin, E. M., Bender, M. A., Demaine, E. D., Fekete, S. P., Mitchell, J. S., & Sethia, S. (2005). Opti …

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:         …