Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
1answer
25 views

How to divide a set of $n$ points of the plane into two subsets so that $ MA_1+ MA_2+ …+MA_k= MB_1+ MB_2+ …+MB_{n-k} $ for some point $M$?

Definition. If a some set of $n$ points of the plane can be divided into two subsets $\{ A_1, \; A_2, \; ..., \; A_k\}$ and $\{ B_1, \; B_2, \; ..., \; B_{n-k}\}$ so that there is a point $M$ of the ...
7
votes
1answer
54 views

Divide the chessboard

Suppose you have marked all the 64 centers of unitsquares of a chessboard. At least how many lines do you need, such that they divide the plane in a way, such that no two marked points lie in the ...
1
vote
1answer
80 views

Partition of a rectangle into squares problem

recently I encountered this problem: "Show that a rectangle can be partitioned into finitely many squares if and only if the ratio of its sides is rational." I have found the a solution which I need ...
0
votes
1answer
16 views

Permutations on a grid with repetition allowed

I understand how to calculate the number of permutations given a latin grid, but this problem is not that. Given a $4\times4$ grid, how many unique ways are there to arrange the numbers $1, 2, 3$ ...
1
vote
0answers
28 views

Maximum number of nodes in a circle, with distance constraint

Given a circle $C$ with known radius $r$, I want to determine the maximum number of nodes in the circle, where there is a distance constraint between each two nodes equal to $s$, i.e. each two nodes ...
7
votes
1answer
76 views

How many vertices can a hypercube-hyperplane intersection have?

Consider the n-hypercube $[-1, 1]^n$, and intersect it with an n-hyperplane. The intersection is in general an $(n-1)$-dimensional polytope. How many vertices can it have? For example, when $n=2$, it ...
1
vote
1answer
34 views

Is packing rectangles exactly into a larger rectangle NP-complete?

I want to pack a number of rectangles into a larger rectangle, however, unlike other questions that I could find, I would like to do so exactly, without allowing any wastage. I do not really care ...
-1
votes
2answers
50 views

Create projective plane

Please explain this https://math.stackexchange.com/a/463369/672948 in a simpler way. I am not from higher mathematics background and these terms are quite hard to understand. I am clear upto finding ...
0
votes
0answers
40 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
1answer
65 views

Understanding a step in an inductive proof that $n$ hyperplanes in $\mathbb{R}^d$ determine $\sum_{0\leq i\leq d}\binom{n}{i}$ cells ($d$-faces)

In the book Lecture Notes on Discrete Geometry by Jirka Matousek, in page 127, a theorem is proved: The number of cells ($d$-faces) in a simple arrangement of $n$ hyperplanes in $\mathbb{R}^d$ ...
7
votes
3answers
153 views

Why is the permutohedron simple?

I am working with the permutohedron in $\mathbb{R}^n$ which is defined as the convex hull of $n!$ vectors as follows: $$\Pi_n := conv\{(\sigma(1), \ldots, \sigma(n))\ |\ \sigma \text{ permutation of }...
0
votes
1answer
25 views

Number of ways to choose a closed path of given length on a square lattice

Also known as self-avoiding polygons, this is an unsolved problem. However, to leading order in the asymptotic limit, the number of polygons of a given perimeter scales exponentially with perimeter ...
0
votes
0answers
26 views

Counting approximations of a flat shape by subsets of square tiling

A closed topological disk $K$ is approximated by the maximal subset of faces of the square tiling that are contained in the interior of $K$. As $K$ is translated and/or rotated in the plane, the ...
2
votes
0answers
39 views

Minimum diameter for $n$ points, given that distance between any two of them is greater than or equal to 1.

There are $n$ points on a plane, such that distance between any two of them $\geq 1$. Question is, what is minimum possible diameter for such set of points, that is minimum of distance between two ...
0
votes
0answers
26 views

Finding maximal antichain in poset of binary strings

Define the partial order on a set $X$ of all binary strings of length n to be $xRy$ if and only if $x=y$ or $x$ has an odd number of ones and $x$ and $y$ are adjacent vertices on the hypercube $Q_n$, ...
0
votes
0answers
9 views

Simple polytopes

I know that a (d dimensional) simple polytope is defined as one such that each vertex is contained in exactly d facets. I heard that an equivalent characterization is that the set of outward edges ...
0
votes
0answers
56 views

Chessboard $8\times8$ covered by $32$ dominoes [duplicate]

We consider a standard 8×8 chessboard and we cover it (completely!) with dominos of size $2×1$ (therefore every domino tile cover exactly $2$ fields). The question is if we can find a cover such that ...
1
vote
1answer
36 views

Quadratic number of flips to Delaunay triangulation

I have this problem. Let $a$ and $b$ two horizontal lines in the plane and a set $S$ of $n$ points distributed half in each one of them. All possible triangles use two points from $a$ and one from $b$...
6
votes
0answers
62 views

Is this kind of “Gerrymandering” NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
1
vote
1answer
39 views

Sylvester Gallai for complex projective plane

I understand that the Sylvester Gallai theorem doesn't hold for the projective complex plane. Can anyone explain why does Kelly's proof: Here doesn't hold for the complex projective plane? A counter ...
0
votes
1answer
39 views

Associating a variety to a cone?

I am remembering this from something I read a while ago, but I'm not sure how accurate this is and I would like clarification and appreciate explanations if possible. Is the following correct? : The ...
0
votes
0answers
21 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
30 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
109 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
32 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
103 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: ...
3
votes
0answers
60 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
29 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
34 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
50 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
179 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 ...
3
votes
1answer
83 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
80 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
74 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
219 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
42 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
75 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
29 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
37 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
129 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
107 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
134 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
40 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 ...
1
vote
1answer
49 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
211 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
83 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
85 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
1answer
49 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
123 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
164 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 ...