Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-geometry]

Combinatorial geometry is concerned with combinatorial properties and constructive methods of discrete geometric objects. Questions on this topic are on packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems.

0
votes
0answers
9 views

Geometry and the vertices of the Birkhoff polytope

The Birkhoff polytope $P(n)$ is defined to be the points in $\mathbb{R}^{n^2}$ which correspond naturally to $n \times n$ doubly stochastic matrices. Is it possible to prove that the vertices of the ...
0
votes
1answer
28 views

Clarification about a given axiom system.

I am now currently studying Combinatorics of Finite Geometries. One problem asks if the given axiom system below is consistent or inconsistent. There are five points and six lines. Each point is in ...
6
votes
1answer
88 views

A formula for the number of possible combinations of a $i\times j$ rectangle in a $m\times n$ grid such that they don't overlap?

Suppose I have a grid of size $m\times n$ and a rectangle of length $i\times j$ where $i$ and $j$ are integers as shown here for where $m = 7$, $n = 5$, $i = 2$, $j = 3$:  Does there exist a ...
1
vote
0answers
21 views

generalization of Dyck Path: size K upward steps

One of the many interpretations of Dyck Paths is the number of lattice paths from $(0,0)$ to $(n,n)$, staying at or below the diagonal $y=x$, using only 2 kinds of line segments (1 unit right, or 1 ...
5
votes
1answer
78 views

Tiling a 7x9 rectangle with 2x2 squares and L-shaped trominos

It's possible to cover a 7x9 rectangle using 0 2x2 squares and 21 L-shaped trominos, for example: ...
2
votes
0answers
52 views

Maximum number of umbrellas that can be added in a one kilometer beach?

Suppose we have a beach of length $1-$km. Suppose one Day $0$, the beach is empty. One day $1$, a family comes and puts their umbrella at some point in the beach. This point is fixed forever and ...
1
vote
1answer
27 views

How many intersecting there's between Diagonals and smaller parts?

If there is a rectangle to the side $a$ and $b$. $(a \leq b)$. Then divide it into $ab$ smaller segments, and then draw the rectangle diameter. How many intersections are there between Rectangular ...
0
votes
1answer
29 views

4 Points with 2 different colors and 2 Lines partitioning the plane - Combinatorial geometry algorithm problem

We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two ...
1
vote
2answers
38 views

A maximal cardinality subset of n lattice points so that all points in the subset have distance at least 4

If we have some random set of $n$ lattice points what is the maximum cardinality of a subset in which all points have distance at least $4$ (or some other number). I really hope the best bound is not ...
11
votes
1answer
172 views

Several rectangles cover the unit square. Can I find a disjoint set of them whose area is at least $1/4$?

I am interested in the following question: Let a finite sequence of rectangles in $\mathbb{R}^2$ be given such that The edges of the rectangles are parallel to the coordinate axes, and ...
2
votes
1answer
67 views

How many different graphs of order $n$ are there?

I'm interested in all four combinations: directed and undirected, cyclic and acyclic. I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number ...
0
votes
0answers
63 views

About “combinatorial topology”, what Munkres covers and a textbook reference request

When a university says they research in "combinatorial topology" what does that mean? I've seen a university in Country A list "combinatorial topology" in its math department's research areas, but I ...
0
votes
0answers
62 views

Example of Proof of Radon's theorem

"By mathematical induction. Let proposition $P_n$ be Helly’s Theorem in the case of n subsets in $\mathbb{R}^d$. Since $n > d$, we can use $P_{d+1}$ as our base case. $P_{d+1}$ is clearly true, ...
7
votes
3answers
180 views

How many $n$-pointed stars are there?

Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars ...
2
votes
1answer
40 views

Bounds on $d$ for tiling $\mathbb{Z}^d$ with subset of $\mathbb{Z}^n$?

According to this remarkable paper by Gruslys, Leader and Tan, given any subset $T$ of $\mathbb{Z}^n$, $\exists d$ s.t. $T$ tiles $\mathbb{Z}^d$. This immediately became one of my favourite ...
2
votes
0answers
64 views

Calculate the number of nonnegative integer solutions of $ax+by\leq c$.

If $a$, $b$, and $c$ are known, and $x$ and $y$ are integers greater than or equal to zero, how many possible values of ($x$, $y$) exist that satisfy the equation $$ax + by \le c\,?$$ I have ...
1
vote
0answers
28 views

Fewest number of distinct distances between $n$ points in $\mathbb Z^2$

I've been thinking about proving some bounds for the OEIS sequence A319476: $a(n)$ is the minimum number of distinct distances between $n$ non-attacking rooks on an $n \times n$ chessboard. I'd ...
0
votes
1answer
24 views

Coloring the plane and the space with four and five colors

Here are two problems, each one is an olympiad combinatorics problem with coloring the plane and space. A) The plane is colored with four colors. Prove that it is possible to choose three different ...
4
votes
2answers
126 views

Strange succession

An ant starts from the origin of a cartesian plane and makes $n \ge 2$ steps of lengh $d_1, d_2, \cdots, d_n$. Is there a condition (necessary and sufficient) on $d_i$'s for which the ant can come ...
1
vote
1answer
105 views

Moscow Seven Sisters

Fix $n$ points in the plane in generic position, i.e. no three of them on the same line, etc. The number of lines joining two of them is ${n \choose 2}$. The number of regions in which $\ell$ lines ...
0
votes
1answer
120 views

Stirling numbers and left right minima

How does one prove that the # of n- element permutations with k left-right minima is given by the 1st kind stirling number? I understand one should consider sigma(1)=n and sigma(1)=/=n, but I am ...
1
vote
0answers
32 views

Moving Point in a set of non-concurrent lines

In a plane we have N lines, no two of which are parallel or perpendicular, and no three of which are concurrent. A cartesian system of coordinates is chosen for the plane with one of the lines as the ...
2
votes
1answer
44 views

Manufacturing desired planks from an existing pile of planks

Suppose there is a pile of commensurable planks that only may differ in lengths $0<a_1\leq\cdots\leq a_m$, which are to be used to manufacture planks of length: $0<b_1\leq\cdots\leq b_n$. ...
1
vote
1answer
205 views

How many components are required for partitioning a square between two colors?

Suppose $n$ disjoint points, some red and some blue, are organized on a line. We want to partition the line to two subsets, one containing all the red points and one containing all the blue points. ...
1
vote
2answers
70 views

How to cut a square on $5$ squares?

We can cut any square on $n$ squares if $n>5$ and $n=4$. The proof is easy by induction. Base cases $n=6,7,8$ are easy to find and then since we can cut a square on $4$ squares we get $3$ new ...
5
votes
1answer
74 views

Ratio between farthest and second farthest distance

$n\geq 3$ points lie in three-dimensional space. What is the largest $c(n)$ such that there always exists a point for which the ratio between the distance to the farthest point from it and the ...
1
vote
2answers
43 views

Partition of a regular polygon

Find the values of $n$ such that there exist a regular polygon with $n$ vertices such that can be partitioned with isosceles triangles with the vertices ...
2
votes
0answers
114 views

Simple disproof of Danzer — Grünbaum conjecture

A set of points in $\mathbb R^n$ is acute if any three points from this set form an acute triangle. In 1962 Danzer and Grünbaum conjectured that cardinality of acute set in $\mathbb R^d$ is $2d-1$, no ...
4
votes
2answers
140 views

Number of ways to distribute objects, some identical and others not, into identical groups

The question I initially thought of that prompted this was "How many distinct integer-sided cuboids are there with a volume of $60^3$?". A small example to clarify: There are $3$ integer-sided ...
1
vote
1answer
56 views

What is the least amount of pieces on a board with the following conditions:

There's an infinite board. Imagine you add a rectangle of $m*n$ pieces. With $m,n \geq 2$ (There's a piece every square, and you can't put one above other.) You can make a piece 'jump' other that is ...
1
vote
2answers
45 views

A is the set of all triangles whose perimeter is 2013. B is the set of all triangles whose perimeter is 2016. Which set has more triangles.

Let A be the set of all triangles whose lengths of sides are integers and whose perimeter is $2013$. Let B be the set of all triangles whose lengths of sides are integers and perimeter is $2016$. ...
1
vote
0answers
24 views

Acute set in three-dimensional space

I'm trying to prove the following statement: Prove that every set of more than $8$ points in the three-dimensional space determines at least one obtuse angle. I'm aware that the generalization of ...
0
votes
0answers
22 views

Maximum Hitting Set of k-uniform Hypergraphs in Planar Graphs

I'm stuck with a problem and wonder whether you can help me. I guess the biggest problem is that I don't even know what I have to google for to find information about my problem. I'll try to explain ...
1
vote
1answer
87 views

Design of a peculiar Wheel of Fortune

Consider the two wheels of fortune illustrated below. The first one (left) is constituted by $c$ sectors with the same arc length: $\alpha$ of which are red, $\beta$ of which are blue and $\gamma$ of ...
5
votes
0answers
45 views

Color the edges and diagonals of a regular polygon

Here is the problem: For what $n$ is it possible to color the edges and diagonals of an $n$-side regular polygon with $\dfrac{\binom{n}{2}}{3}$ colors, such that you use every color exactly three ...
1
vote
1answer
76 views

Looking for help developing an algorithm to solve a 2D rectangle packing/bin problem.

I need to develop an algorith to determine the optimum packing arrangement of dimensionally identical rectangles in a large rectangle of fixed size. 90 degree rotations are permitted. I've researched ...
1
vote
0answers
51 views

Does a circle give the largest smallest distance between two points that bisecting the perimeter

The title may seem a bit confusing, let's use math notation. Let $c:\mathbb{R}\to \mathbb{R}^2$ be a simple closed curve parametrized by length. A pair of points on the curve that bisect the ...
1
vote
2answers
74 views

Are (quasi-)regular polytopes uniquely determined by their edge graph?

I consider polytopes $P\subset\Bbb R^n,n\ge 2$ of arbitrary dimension (intersection of finitely many halfspaces, therefore convex), which are vertex- and edge-transitive (also called quasi-regular). ...
1
vote
0answers
45 views

Combinatorial question on the arrangement of hyperplanes

Let $l,m\in\mathbb{N}_+$ and define $\Theta(l,m):=\mathbb{R}^{m\times l}\times \mathbb{R}^m$ to be the set of tuples of a $m\times l$ matrix and a vector of length $m$. Definition of $v_\theta$ and $...
2
votes
1answer
34 views

Restore coordinates from triplets of distances around central point

I have $n$ points in $\mathbb{R}^3$ with one point called 'central'. I can write out side lengths of all triangles that contains this central point (side that is not lie on central point always comes ...
2
votes
2answers
72 views

Number of intersections formed by $m$ circles and $n$ straight lines

Suppose there are $m$ circles and $n$ straight lines in the plane. Find the maximum number of regions formed by them. I think that the question is self-explanatory, otherwise, I'll explain it ...
2
votes
1answer
32 views

compute f-and h-vector of simplicial complex

A simplicial complex $\Delta$ is uniquely determined by its facets $\mathcal{F}(\Delta)$. I know how to compute the $f$-vector and therefore the $h$-vector given all the faces of $\Delta$. Now given ...
0
votes
1answer
97 views

The VC dimension of convex d-gons

The VC dimension of convex $d$-gons is $2d+1$. To show that, I can prove the lower bound is $2d+1$. however, I don't know how to prove the upper bound in a rigorous way. For low bound, I construct a ...
2
votes
2answers
45 views

no three points in a line on $\mathbb{Z}_p^2$

in finite geometry, the $\mathbb{Z}_p$-plane is $\mathbb{Z}_p^2$, I have proved there are exactly $p+1$ lines pass through a given point in $\mathbb{Z}_p^2$, and by this conclusion there are at most $...
2
votes
0answers
70 views

Probability of hypercube vertices being within the unit n-hypersphere

Three uniformly distributed i.i.d points inside the unit n-ball centered at the origin are picked $p_1, p_2, p_3$ they are chosen such that $\|p_1\|>\|p_2\|,\|p_3\|$ , where $\|p\|$ is the ...
1
vote
2answers
46 views

Comparison of the numbers of colored squares in a checkerboard colored with red green and blue

The squares of a checkerboard $n \times n$ are colored alternatively in red, blue and green so that: next to a red square, there is a blue square; next to a blue square, there is a green square; next ...
3
votes
1answer
52 views

Splitting a shape into a number of congruent shapes similar to the original; analogues to A4 paper system

Two A4 papers can be put side by side to create a new rectangle that is similar to the original rectangles. Similarly, 5 right triangles with the length ratio between legs of 1:2 can be put to ...
1
vote
0answers
47 views

Can we paint the plane in two colors such that there is no square of the same color? [duplicate]

We have our every day plane $\mathbb{R}^2$ which we want to paint using two colors in such a way that no four points form a square of the same color. This means that for any square on the plane its ...
2
votes
0answers
36 views

What breaks down in the theory of affine hyperplane arrangments?

It appears to me that there is a substantial amount of combinatorial algebra and geometry supporting the theory of central hyperplane arrangements (See Topics in Hyperplane Arrangements, Aguiar and ...
2
votes
0answers
37 views

Covering the plane by circles centered on a discrete set

I have the following combinatorial/discrete analysis problem that arose while I was working on a problem in complex analysis, which in turn came from a problem in time-frequency analysis. Let $\...