New answers tagged computational-geometry
0
This task interested me, at least in non-degenerate case. I've tried to google it and suddenly found a beautiful approach described here (starts with "Next, the constraints are added to the Delaunay triangulation...", but we don't care about Delaunay here).
Name the set of segments $S$. First, forget about segments and build any triangulation $T$ of all ...
1
I'd like to propose a variation on Aleksandr Logunov's proof, that I find to be a bit simpler (arguable).
Let's prove that we can make a tree from a collection of disjoint trees.
So suppose we have a collection of at least two disjoint trees in the plane (if there were only one we would be done).
Without loss of generality, suppose that no two vertices ...
1
Disclaimer: the proof is quite technical. OTOH, I don't see a comfortable way to do this, because the initial set of segments can be as crazy as possible, even if none of them intersects.
Let's prove that we can make a tree not only from the set of disjoint segments, but also from the set of disjoint trees. So, the initial statement will be just a special ...
4
Here is a simple counter example :
You most join the two leftmost vertices to the two middle vertices, and both ways to do that don't work.
2
The edges of a Voronoi diagram are the curves at equal distance from two geometric entities.
for two points, the mediatrix,
for two lines, the bissectrix,
for a line and a point, a parabola,
for two circles, a general conic.
The vertices are the intersections of two equidistant curves.
The diagram can also be seen as the set of crest lines of the distance ...
2
The Voronoi diagram of disjoint segments (b) has been thoroughly studied.
Image from GIS.
See:
CGAL Manual, Chapter 43:
2D Segment Voronoi Diagrams. CGAL link.
For the Voronoi diagram of circles (d), see:
Jin, Li, Donguk Kim, Lisen Mu, Deok-Soo Kim, and Shi-Min Hu. "A ...
2
An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.
3
Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.
As the Voronoi diagram is the dual of the Delaunay triangulation, this is the same as asking if the edge $xy$ is in the Delaunay triangulation of $P$.
You might know the following characterisation:
An edge $(a,b)$ is in the Delaunay ...
1
I thought I would offer the brute force solution.
The idea is to try every single track layout in turn. When constructing a layout, there are only three pieces that need to be taken into consideration: a left handed curve, a right handed curve and a straight.
You can encode the track layout as a base 3 number with a width corresponding to the number of ...
-2
Assume that you start at the point (0, 0) going straight to the right. You need to add tracks until you reach the point (0, 0) again, this time straight from the left. There are two problems here: One is to reach the point (0, 0) coming from the left exactly. The other is to have no overlaps.
To form a counter-clockwise circle you will need 12 curved ...
2
Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints,...
2
The online version can be solved in $O(n\log n)$ amortised time, possibly using the technique you already came up with. The key is to maintain just the nonoverlapping intervals that result from merging intervals wherever necessary.
Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, ...
4
Firstly, a frame challenge:
A computer can create a valid layout using all of the tracks and if the algorithm is good, perhaps in a few seconds
You don't need the algorithm to run in a few seconds. You need output in a few seconds. I don't see that there's anything stopping you from setting a brute force layout cruncher running on a computer in the ...
4
One possible solution to make this as simple as possible to quickly get a working algorithm would be as follows. The simplest layout is of course 12C (12 curved tracks all with the same orientation (relative to each other), and forming a simple circle. This will be the basis upon which we can build on.
So the basic algorithm will be to maintain the 360 ...
1
Assuming that the query line is long, you could split it into small pieces (let's talk about 'long' and 'small' later).
For each segment you calculate the bounding box and then you can query with that bounding box any tree that stores AABBs (R-Trees/BVH, Quadtrees, ....).
For each result you will have to check manually whether it really intersects with your ...
3
Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$:
Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).
2
If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $(y,z)$-plane and answer the following question:
Given $n$ axis aligned rectangles and a query point $p$, report the rectangles containing $p$.
To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that ...
Top 50 recent answers are included
