20
$\begingroup$

Let $h(n)$ be the largest number of mutually invisible points that can be located in a polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment $xy$ contains a point strictly exterior to the closed set $P$.
   Hidden456
I have a vague sense that this question—What is $h(n)$?—may have been studied before, and perhaps even entirely resolved, but I am not recalling references. Any help would be appreciated—Thanks!


Answered by Wlodek Kuperberg:
 HiddenN
The same construction shows that $h(n)=n-3$ for hiding points in a polyhedron of $n$ vertices in $\mathbb{R}^3$.

$\endgroup$
4
  • 10
    $\begingroup$ If $k$ points are mutually invisible in an $n$-sided poygon, then no two of them lie in the same triangle of a triangulation. Therefore $h(n)\le n-2$, and there is a simple example, generalizing your construction for $n=4$ and $5$, of an $(n+2)$-sided polygon with $n$ mutually invisible points in it, for every $n$: Draw a concave-up arc of a circle tangent to your "V" at its upper ends and place $n$ vertices on it. Place your red points very close to the midpoints of the chords of the circular arc. Unless I misinterpret your question, this shows that $h(n)=n-2$ for every $n\ge3$. $\endgroup$ Nov 2, 2013 at 1:36
  • 2
    $\begingroup$ @WlodekKuperberg: Ah, Yes!, simply a reflex chain of $n-2$ edges, completed with two more edges. Nice proof---Thanks! $\endgroup$ Nov 2, 2013 at 1:42
  • 7
    $\begingroup$ @WlodekKuperberg, you should write that as an answer! $\endgroup$ Nov 2, 2013 at 4:36
  • 1
    $\begingroup$ @W.K.--you have provided examples of polygons for which convex coverings cannot have fewer members than any triangulation; an example for each number of sides. $\endgroup$ Nov 2, 2013 at 5:18

1 Answer 1

14
$\begingroup$

OK - following the suggestion of Mariano Suárez-Alvarez, a moderator - I post my comment as an answer:

If k points are mutually invisible in an n-sided poygon, then no two of them lie in the same triangle of a triangulation. Therefore $h(n)≤n−2$, and there is a simple example, generalizing your construction for $n=4$ and $5$, of an $(n+2)$-sided polygon with $n$ mutually invisible points in it, for every $n$: Draw a concave-up arc of a circle tangent to your "V" at its upper ends and place $n$ vertices on it. Place your red points very close to the midpoints of the chords of the circular arc. Unless I misinterpret your question, this shows that $h(n)=n−2\ \ $ for every $n≥3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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