3
$\begingroup$

Suppose that the interiors of $n$ $m$-sided planar simple closed polygons generate a $\sigma$-algebra $A$.

How many atoms can $A$ possess, at the most?

Failing an exact answer, how about good bounds?

$\endgroup$
3
  • $\begingroup$ No idea, but my colleague, Frank Ruskey has done a lot of work on Venn diagrams with various conditions. Maybe look at some of his work? $\endgroup$ May 27, 2014 at 3:54
  • $\begingroup$ Why is this a $\sigma$-algebra? I mean as there are only finitely many polygons, this is the same as the algebra generated by them, right? $\endgroup$
    – domotorp
    Jul 2, 2014 at 11:14
  • $\begingroup$ Meanwhile, see the awesome symmetrical polygonal Venn diagrams of Rusky, Savage and Wagon in their AMS Notices cover article here: ams.org/notices/200611/ea-wagon.pdf#page=8. $\endgroup$ Jul 2, 2014 at 20:55

1 Answer 1

2
$\begingroup$

If I understood your question correctly, you want a bound on the primal shatter function of $m$-gons. For a little intro to the notion, see e.g., http://www.cs.cornell.edu/courses/cs4850/2009sp/Scribe%20Notes/Lecture%2034%20Monday%20April%2013.pdf

or Matousek's book: http://books.google.hu/books?id=QS6vnl8WlnQC&pg=PA984&lpg=PA984&dq=shatter+func+matousek&source=bl&ots=4BECUUrDge&sig=lftBHslLFq_s0bJVQBCW9Si1jPA&hl=en&sa=X&ei=JuyzU7aSOIfY7AaTrYDwCw&ved=0CB4Q6AEwAA#v=onepage&q=shatter%20func%20matousek&f=false

It is not hard to prove that the VC-dimension of convex $m$-gons is $2m+1$, so the answer to your question would be about $n^{2m+1}$.

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