We prove that the largest convex shape that can be placed inside a given convex shape $Q subset mathbb{R}^{d}$ in any desired orientation is the largest inscribed ball of $Q$. The statement is true both when largest means largest volume and when it m
eans largest surface area. The ball is the unique solution, except when maximizing the perimeter in the two-dimensional case.
Given n data points in R^d, an appropriate edge-weighted graph connecting the data points finds application in solving clustering, classification, and regresssion problems. The graph proposed by Daitch, Kelner and Spielman (ICML~2009) can be computed
by quadratic programming and hence in polynomial time. While a more efficient algorithm would be preferable, replacing quadratic programming is challenging even for the special case of points in one dimension. We develop a dynamic programming algorithm for this case that runs in O(n^2) time.
Let $C$ be the unit circle in $mathbb{R}^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation pro
blem on $C$, where we want to place $kgeq 1$ emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1leq kleq 7$ what the optimal set of shortcuts is. Interestingly, the minimum diameter one can obtain is not a strictly decreasing function of~$k$. For example, with seven shortcuts one cannot obtain a smaller diameter than with six shortcuts. Finally, we prove that the optimal diameter is $2 + Theta(1/k^{frac{2}{3}})$ for any~$k$.
Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact.
(1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any $3$-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the $1$-skeleton of any $3$-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.
Given four congruent balls $A, B, C, D$ in $R^{d}$ that have disjoint interior and admit a line that intersects them in the order $ABCD$, we show that the distance between the centers of consecutive balls is smaller than the distance between the cent
ers of $A$ and $D$. This allows us to give a new short proof that $n$ interior-disjoint congruent balls admit at most three geometric permutations, two if $nge 7$. We also make a conjecture that would imply that $ngeq 4$ such balls admit at most two geometric permutations, and show that if the conjecture is false, then there is a counter-example of a highly degenerate nature.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of
edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from the
ir Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
