3
$\begingroup$
  1. Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C?

Note 1: In question 1, smallest could mean least area or least perimeter. So, one can also ask which C maximizes the difference between its least area and least perimeter convex centrally symmetric container.

  1. Given a convex planar region C, how does one find/characterize the largest zonogon contained within C?

Guess: At least the largest area internal zonogon of C seems to have its center on the medial axis of C. Not sure about the least perimeter one - this zonogon could degenerate into a zero area one in some cases.

Note 2: Analogous questions can be asked about axisymmetric containers - and containees - of C.

Note 3: Some similar questions are recorded at Curves of constant width that contain triangles, Smallest triangles that contain 2D convex regions with reflection symmetry and linked pages.

$\endgroup$

1 Answer 1

4
$\begingroup$

Question 1, in the minimum-area setting, has been studied by Guibas, Nguyen and Zhang (SODA 2003). They prove the following algorithmic result:

Theorem 4.5 The minimum area zonotope containing a set of $n$ points in $\mathbb{R}^2$ can be computed in $O(n \log^2 n)$ [time].

If you set the center of the zonotope at $O$, then the zonotope must contain the original vertices (of your convex polygon) and their reflections (with respect to $O$), and the minimum-area solution is the convex hull of those two point sets. So you can define a function $f$ that maps $O$ to the minimum area. They prove that this area function is unimodal and piecewise affine, and they design an efficient algorithm that finds its minimum.

Guibas, Leonidas J.; Nguyen, An; Zhang, Li, Zonotopes as bounding volumes, Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 803-812 (2003). ZBL1092.68697.

(A freely available version of their paper is in ResearchGate.)

Here is an illustration by myself of a minimum-area zonogon around a triangle. The contours illustrate zonogon area as a function of the centerpoint $O$. Observe that the function is indeed piecewise affine (as proven by Guibas et al.), and that somewhere inside the input triangle, there is a nonzero-size region (dark blue) where the area function attains its minimum, so $O$ can be chosen freely from that area (here: randomly).

Zonogon around triangle

$\endgroup$
1
  • $\begingroup$ Thanks. Hopefully the other aspects of question 1 and question 2 have similarly nice answers. $\endgroup$ Feb 14 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.