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.

Filter by
Sorted by
Tagged with
1
vote
1answer
54 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
221 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
107 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
99 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
52 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
140 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
195 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 ...
2
votes
1answer
95 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
53 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
30 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 ...
1
vote
1answer
211 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
77 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
338 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
57 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
98 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
46 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
59 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
248 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 ...
0
votes
1answer
83 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
1k 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
65 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
105 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
130 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
320 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
59 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
1answer
56 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
38 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 $\...
4
votes
1answer
281 views

Explaining recurrence for number of no-leaf subgraphs in $2 \times n$ grid.

Consider the number of leaf-free subgraphs of the $2 \times n$ grid—which is to say, the number of ways to draw lines on the $2 \times n$ grid such that no grid point has degree exactly 1. For ...
4
votes
1answer
141 views

Fit a set of rectangular blocks given in a random order into a minimum volume box

Given a set of blocks whose length, width, and height respectively are $A:1 \times 3 \times 2$, $B: 2 \times 2 \times 1$, $C \text{ and } D: 2 \times 1 \times 1$, and $E,F,G\text{ and }H: 1 \times 1 \...
1
vote
0answers
31 views

Circuit(cyle)-hyperplanes in a graph

Im currently working in matroid theory problem involving graphs. A circuit-hyperplane in a matroid is a circuit with |r| elements in a Flat of |r-1|. Translated into a graph the circuit-hyperplane ...
0
votes
1answer
238 views

Finding the dimensions of a Hypercube by the number of its edges

What is the dimension of a hypercube with 524,288 edges? I know that for $Q_n$, the number of edges is $(\frac{1}{2})n2^n = n2^{n-1}$. So I wrote this down in my book: $$(\frac{1}{2})n2^n = n2^{n-1}...
0
votes
1answer
307 views

How many of the triangles in a regular polygon of 18 sides are isosceles but not equilateral?

Let $A_1,A_2,.....,A_{18}$ be the vertices of a regular polygon with $18$ sides. How many of the triangles $\Delta A_iA_jA_k,1\le i<j<k\le 18$, are isosceles but not equilateral? A. $63$ B. $...
3
votes
1answer
450 views

Radius of inscribed sphere of n-simplex.

I want to calculate the radius of inscribed sphere of $n$-simplex, where the side length of $n$-simplex is 1. For example, when $n=2$, the 2-simplex is equilateral triangle with side length is 1. ...
4
votes
1answer
94 views

Prescriptive version of counting hyperplane arrangements

In Hyperplane arrangement theory, Zaslavsky's Theorem necessarily bounds the number of bounded and unbounded regions in the complement of a real hyperplane arrangement. While this counting theorem is ...
2
votes
0answers
92 views

A problem in elementary combinatorial space geometry.

Also asked on overflow: https://mathoverflow.net/questions/296567/some-elementary-schubert-calculus-calculations/296583#296583 Consider $3$ dimensional projective space (although you don't have to ...
9
votes
0answers
360 views

Prove 2017 points in a plane cannot form 2017 triangles with the largest area

I haven’t got an idea about this problem . Could someone help me? Suppose 2017 points in a plane are given such that no three points are colinear. Among the triangles formed by any three of these ...
2
votes
0answers
68 views

Cutting disk into more than 8 parts of equal area by 4 lines

Is it possible to cut unit disk in more than 8 parts of equal area (possibly not congruent) by 4 lines? It's can be proved that it's impossible to cut circle in 7 parts by 3 lines. For example, here ...
2
votes
0answers
85 views

How many ways can hexagonal tiles of side a be arranged in a b*a sided triangle?

How many ways can hexagonal tiles can be arranged in a triangle? Let us assume that there is an equilateral triangle of side $s$. The triangle is subdivided by edges on $b$ segments, so that there ...
3
votes
0answers
41 views

Subsets of the circle not contained in a semi-circle

I'm reading a paper (Bullett and Sentenac, "Ordered orbits of the shift...", Ergodic Theory and Dynamical Systems), and have found that a proposition (Proposition 1) is (1) slightly incorrect (I have ...
2
votes
2answers
160 views

Proving that the area of a polygon is less than $\pi/4$

The sides and diagonals of a (not necessarily convex) polygon have length at most $1$. Prove that the area of the polygon is less than $\dfrac{\pi}{4}$. I was able to prove that the area must be ...
0
votes
1answer
32 views

Existence of a Broken Line with Length at most $2n$

Inside a unit square $n^2$ points are placed. Prove that there exists a broken line that passes through all these points and whose length does not exceed $2n$. I've been trying to solve this problem ...
2
votes
0answers
33 views

Contraction of oriented matroid as related to polytope?

I'm reading the following description of the contraction of oriented matroid, and its connection to polytopes: I have yet to find a numerical example to verify 6.13., but first I just want to check ...
3
votes
0answers
104 views

Relationship between Affine Dependence and Linear Dependence in Oriented Matroids?

I'm reading "Lectures on Polytopes" by Gunter Ziegler. The author first introduces the components of oriented matroids in affine case, then making a transition to linear case, with the condition "1z ...
1
vote
0answers
56 views

Why are there topological no results on halfspace arrangements?

After doing some searching around, I've come to realize that while there is a huge body of literature on hyperplane arrangements, not much is generally written about halfspace arrangements. Is there ...
13
votes
1answer
335 views

What is the exact value of the radius in the Six Disks Problem?

The disk covering problem: Find the smallest radius $r(n)$ required for $n$ equal disks to completely cover the unit disk. For $n=5,6$, the best layouts are, $\hskip2.2in$ $\hskip2.2in$ with $r(5) \...
2
votes
1answer
169 views

How many right triangles can be constructed?

A right triangle $PQR$ is to be constructed in the $xy$-plane so that the right angle is at $P$ and line $PR$ is parallel to the $x$-axis. The $x$ and $y$ coordinates of $P$, $Q$ and $R$ are to be ...
1
vote
1answer
2k views

Number of paths in a grid below a diagonal [closed]

Given there is a $n\times n$ square grid . I was trying to calculate the number of paths from $(0,0)$ to $(n,n)$ under the condition that one might move either up or to the right one step at a time. ...
26
votes
1answer
549 views

The generous lazy caterer

It is well-known that $n$ chords divide any convex shape into at most $\frac{n^2+n+2}2=T_n+1$ regions – the lazy caterer's sequence. For example, the pancake below is cut into seven pieces by three ...
1
vote
2answers
142 views

Find the maximum possible number of points of intersection of perpendicular lines

I know many such questions have already been asked but this one seemed to be a very messy and a lengthy question for me to solve. The question is as follows Consider seven different points $P_1,...
3
votes
0answers
196 views

A Combinatorial Geometry Problem With A Solution Using Extremal Principle

I have solved this following Combinatorial Geometry Problem using extremal principle.Please check whether this solution is correct or not.Also write if you have any other solution. Problem :- Let $...

1 2 3
4
5
14