All Questions
7
questions
3
votes
1
answer
80
views
Maximal cliques on graphs on the vertices of regular $2n$-gons
Consider the vertices of a regular $2n$-gon in the plane, and label the points clockwise $1,\dots,2n$. For any vertex $v$ let $-v$ denote its opposite vertex on the polygon.
Define a graph $G$ which ...
- 2,454
3
votes
2
answers
577
views
Catalan numbers in polygons
I'm stuck on such problem: triangulation of the $n$-gon is division of said $n$-gon into $(n-2)$ triangles whose sides are either sides of the $n$-gon or certain non-intersecting diagonals. How many ...
- 49
9
votes
1
answer
460
views
Number of chords in a $n$-gon if each chord is crossed at most $k$ times
Consider an $n$-gon where we denote the points by $v_1, \dots, v_n$.
If we allow each chord (internal edge of the $n$-gon) to have at most $k$ crossings, how many chords can we put into the $n$-gon (...
- 61
2
votes
1
answer
606
views
The travelling salesman problem for a regular n-gon
The TSP asks, given a finite set $V$ of points in $\Bbb R^2$, to find the shortest path that passes through all points and returns to the starting point. Trivially, one reduces to the case of a path ...
- 27.7k
1
vote
1
answer
83
views
Moving between polygons drawn within a convex polygon with parts of diagonals
My question is about one problem given in last round of codeforces, pretty easy to handle it, but I do not understand the other players` solutions.
We have a convex polygon and numbers it's ...
- 663
3
votes
1
answer
185
views
Labeling the vertices of a polygon with 0's and 1's
Suppose $P_n$ is the regular polygon with n vertices ($n\geq 5$). Let $V=\{v_1,\ldots,v_n\}$ be the vertex set. I would like to define a labeling function $\ell:V\to \{0,1\}$ so that $\sum_{i=1}^{n}\...
- 1,568
1
vote
1
answer
195
views
Corresponding Triangulations of an (n+2)-gon to n Segments Connecting n+1 Collinear Points
So I'm asked to count the number of ways of connecting n+1 collinear points with n line segments subjected to the following constraints:
If the line is L
1) No segment passes below L.
2) Starting at ...
- 4,093