New answers tagged computational-geometry
2
If there would be a polynomial time algorithm for your problem, it could be used to solve the NP-hard recognition problem in polynomial time by just giving the input to it and checking if its output is correct. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP.
(Here we assume that the input is some ...
2
If your initial set of polygons is a power-diagram, you can insert a new polygon by inserting a new center and growing its power circle smoothly. You don't have direct control of the polygons but rather of the underlying power circles. Power diagrams as Voronoi diagrams are always made of convex polygons.
https://diglib.eg.org/bitstream/handle/10.2312/...
0
First, suppose there is at least one triangle in the set. Now the complex is pure if and only if all vertices are contained in some triangle, because any edge that is a facet contains at least one vertex. This is simple to check: iterate over all triangles and mark all vertices contained in them. If there are no unmarked vertices, the complex is pure. ...
0
It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.
instead of minimizing the distance [$t$], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?
Observe that we may assume the maximum allowed distance $t=1$, ...
3
Use a Voronoi diagram of the line segments
As @D.W. noted, a Voronoi diagram of line segments1 is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of Computational Geometry by de Berg et al. ...
1
If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries.
For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-...
2
I haven't tried to work out the details, but it seems plausible to me that it might be possible to solve this with a sweepline algorithm, with ideas from the Bentley-Ottman algorithm.
In particular, one approach would be to build the Voronoi diagram of the line segments (rather than a Voronoi diagram of points, as we usually do), then store it in a data ...
Top 50 recent answers are included
