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.

0
votes
0answers
20 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
7 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
50 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
34 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
56 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
31 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
37 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
16 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
100 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
29 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
95 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
58 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
28 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
46 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
173 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
70 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
69 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
63 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
204 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
41 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
72 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
36 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
127 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
131 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
38 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
48 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
207 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
76 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
82 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
44 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
118 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
149 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
71 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
46 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
25 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
24 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
107 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
47 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
103 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
52 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
75 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
37 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
88 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
35 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
150 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 ...