All Questions
Tagged with co.combinatorics plane-geometry
28 questions
0
votes
0
answers
44
views
Lattice points in the boundary of a Minkowski sum of two convex lattice polygons
Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$.
The equality $...
- 183
13
votes
3
answers
3k
views
Koebe–Andreev–Thurston theorem - where can I find a proof?
Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
- 13.6k
3
votes
1
answer
237
views
Find the number of triangles in plane
Let $S$ be a set of $n$ points in the plane in general position. Each 3 points of S span a triangle. Total number of triangles spanned by S:
$$\binom{n}{3}=\frac{n(n-1)(n-2)}{6}=\frac{1}{6} n^3-O(n^2 )...
- 109k
4
votes
1
answer
356
views
Left and right halves of convex curve
Let $S$ be a set of $n$ points in the plane in general position (no 3 on a line), $n$ even.
A halving line is a line through $2$ points of $S$ that partitions $S$ into 2 equal parts ($(n-2)/2$ points ...
- 60.5k
6
votes
1
answer
127
views
Convex planar regions with all area bisectors having equal length
Following A claim on the concurrency of area bisectors of planar convex regions, let me record a couple of simple queries.
An area bisector (perimeter bisector) of a planar convex region is a chord ...
- 37.7k
18
votes
2
answers
979
views
Arrangements of points in the plane
Let $p_1,\ldots,p_n$ be a collection of distinct points in $\mathbb{R}^2$, no three of which lie on a line. For each $p_i$, let $\omega_i(p_1,\ldots,p_n)$ be the following ordered list (well-defined ...
- 1,446
3
votes
1
answer
329
views
Planar subsets with many pairs of points on distance $1$ [duplicate]
Let $X$ be a subset of $\mathbb R^2$ consisting of $n$ distinct points. Let $d_1(X)$ be the number of pairs of points of $X$ on distance $1$ from each other. Define
$$d_1(n)=\sup_{X\subset \mathbb R^2|...
- 6,367
2
votes
1
answer
84
views
What is the average component size of a coloring?
Supose each cell of a big (or infinite) grid is colored at random by one of $k$ colors. Then the connected monochromatic components (here components are not supposed to contain "wasp waists",...
- 4,589
5
votes
0
answers
235
views
Arrangement of points, lines, and planes
Is it possible to construct a finite nontrivial arrangement of points, lines, and planes in 3-dimensional Euclidean space with the following properties?
every line is incident with four points and ...
- 1,444
22
votes
1
answer
886
views
Happy ants never leave compact domain?
I am curious if the following seemingly simple question has an easy answer?
Consider an ant population of $N$ ants that lives in $\mathbb R^2$. Each ant can be labeled by some coordinate $x\in \mathbb ...
- 148k
14
votes
2
answers
878
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
- 18.8k
5
votes
1
answer
176
views
Orientations of triples of points in the plane
Given a finite indexing-set $I$ and a collection $P = \{P_i: \ i \in I\}$ of points in the plane no three of which are collinear, let $I_{(3)}$ denote the set of ordered triples of distinct elements ...
4
votes
2
answers
94
views
Finding a not too slim triangulation with prescribed vertices on $\mathbb R^2$
Let us fix a constant $r>1$. Let $d(x,y)$ denote the distance between points $x,y\in \mathbb R^2$. Suppose we have a discreet subset $X\subset \mathbb R^2$ such that
1) For any two points $x,x'\...
- 131
10
votes
1
answer
1k
views
How can we find n points on a plane so that as many pairs of points as possible have the same distance?
There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.
- 159
28
votes
6
answers
2k
views
How fast are a ruler and compass?
This may be more of a recreational mathematics question than a research question, but I have wondered about it for a while. I hope it is not inappropriate for MO.
Consider the standard assumptions ...
- 63.9k
21
votes
0
answers
441
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 5,409
6
votes
1
answer
429
views
Bichromatic pencils
A pencil is a collection of some lines through a point, called the center of the pencil.
If the points of the plane are colored, then call a pencil bichromatic if there is a color that is present on ...
- 18.8k
10
votes
0
answers
497
views
Which finite sets could be packed into a square?
This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space.
The problem starts with a two-...
CommunityBot
- 1
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 13.6k
4
votes
0
answers
164
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...
- 48.9k
16
votes
2
answers
1k
views
Are Penrose tilings universal? Do aperiodic universal tilings exist?
Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile ...
- 4,713
10
votes
1
answer
277
views
Optimization of points on a plane
Suppose we have $n$ points on a plane. Let $D$ be the sum of the squares of all the pairwise distances between the points. Let $A$ be the area of the convex hull. What is the minimum possible value of ...
- 15.8k
13
votes
1
answer
247
views
Complexity of planar scissor congruence
Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces.
What can be said about the ...
CommunityBot
- 1
12
votes
1
answer
861
views
Connected components $0-1$ matrices
Let $M$ be a $0-1$ matrix.
Here a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where ...
CommunityBot
- 1
2
votes
1
answer
305
views
Distribution of area of randomly placed circles
I've searched the web now for ages to try and find a paper on the asymptotic distribution of the area of the union of randomly placed discs on the plane. Ideally, I would be looking for the discs to ...
- 6,210
20
votes
1
answer
452
views
Hidden points in polygons
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 ...
- 7,276
3
votes
1
answer
672
views
Gluing Polygons
Consider all polygons whose vertices are lattice points and edges are parallel to the axes such that no more than two edges meet at a vertex. For two polygons A and B, define A+B be to the set of ...
- 22.3k
2
votes
3
answers
2k
views
Placing Axis-parallel rectangles on 2-D plane
Can we place $n$ axis-parallel rectangles on 2D plane (e.g. four sides of each rectangle must be parallel to either x-axis or y-axis) such that for every pair of rectangles, there is a region that is ...
CommunityBot
- 1