All Questions
17 questions
11
votes
1
answer
410
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 17k
6
votes
1
answer
508
views
How many triangulations of a regular octahedron are there, without introducing new vertices?
It is easy to find three triangulations, each consisting of four tetrahedra. Are there more?
- 61
6
votes
2
answers
999
views
The straightest possible path embeddable in a path of polygons
I'm studying a problem involving the sets of discrete curves that can be embedded in a non-trivial polygon, from a source to a target point, as shown below.
Initially my interest was limited to the ...
- 661
5
votes
1
answer
255
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 20.2k
5
votes
2
answers
630
views
Average vertex degree in finite Delaunay triangulations in high dimensions
In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...
- 343
5
votes
1
answer
261
views
Do random triangulation edge-flips maintain randomness?
Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...
- 151k
4
votes
2
answers
818
views
Convex hull in a discrete space [closed]
I know some algorithms which compute the convex hull in a continuous space.
Are there efficient algorithms to compute it in a discrete domain?
For example in 3D discrete space, given the blue points, ...
- 49
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 ...
- 214
3
votes
0
answers
391
views
Dissection of a polygon into convex polygons
Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...
- 935
2
votes
1
answer
270
views
Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane
I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...
- 51
2
votes
1
answer
349
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
- 159
2
votes
0
answers
126
views
Checking existence of a non-crossing Hamiltonian path in geometric graphs
I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...
- 1,305
1
vote
1
answer
178
views
Inside-out dissections of solids -2
We record some general questions based on
Inside-out dissections of solids
Inside-out dissections of a cube
Can every convex polyhedral solid be inside-out dissected to a congruent polyhedral solid?...
- 5,979
1
vote
0
answers
93
views
Inside-out dissections of a cube
Ref:
Inside-out polygonal dissections
Inside-out dissections of solids
Definitions: A polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 5,979
1
vote
0
answers
89
views
Bounds for minimax facility location in a convex region
An earlier question: Facility location on manifolds
A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2
The minimax facility location problem ...
- 5,979
1
vote
0
answers
111
views
On finding optimal convex planar shapes to cover a given convex planar shape
Covering a specific convex shape S with n copies of another specified convex shape S' (which may be different from S) is well studied - for example, https://erich-friedman.github.io/packing/index.html....
- 5,979
0
votes
0
answers
63
views
Bounds for the Dispersal Problem in convex regions
We add a bit to: Bounds for minimax facility location in a convex region
Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...
- 5,979