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$.

Improve this question
$\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$
    – Wlodek Kuperberg
    Commented 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$
    – Joseph O'Rourke
    Commented Nov 2, 2013 at 1:42
  • 7
    $\begingroup$ @WlodekKuperberg, you should write that as an answer! $\endgroup$
    – Mariano Suárez-Álvarez
    Commented 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$
    – Włodzimierz Holsztyński
    Commented Nov 2, 2013 at 5:18

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .