4

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated. Implicit inequalities The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$. Let $a^i x \leq b_i$ for $i\in M$ be the linear ...


4

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by all intersections of unit disks, ...


3

If I understand this correctly, most spatial indexes could be used. Spatial indexes typically have about $O(log{V})$ insertion time and similar lookup time for nearest neighbors. Of course you can create a Voronoi diagram from that, but you can also use the index directly to find the closest neighbors whenever you need them. For low dimensionality (2D, 3D)...


3

It seems that the relevant data structure might be a dynamic Voronoi diagram. Voronoi diagrams are often the answer when a set of points on the plane is involved. In this case, since the point set is evolving, you want a dynamic version.


3

Find any line containing $\geq 3$ points. Delete all points on this line. Repeat. This is a $3$-approximation, since on any line containing $m\geq 3$ points we must delete at least $m-2\geq 1$ points and we delete at most $2$ points too many. Meanwhile, the objective value decreases by at least $m-2\geq 1$. If we know that the true objective value is $K$, ...


3

For all $k=1, \dots, n$, you can easily generate all bit strings of length $n$ with exactly $k$ bits set. The lexicographically smallest bit string has the $k$ ones in the $k$ least significant bits. If you interpret this string string as an integer, and it fits in a constant number of words, you can use bit tricks to find the next string in a constant ...


3

This problem has been studied since 2002, under the name minimum-length corridor problem. The problem is known to be NP-complete[1,2], but there is a constant factor polynomial time approximation algorithm[3]. There is more work on this problem, which you can find by searching the citation network of the papers below. [1]: GONZALEZ-GUTIERREZ, Arturo; ...


3

If $B$ is empty, just pick a single circle. Otherwise, here's a way to turn this continuous problem into a discrete (but still probably hard) problem: Lemma: There exists an optimal solution in which every circle falls into one of the following cases: It has diameter zero and is centred on an $A$-point. It has at least 2 $A$-points on its boundary, and ...


3

The following algorithm will find some set of circles, containing all the points in the set $A$ except all the points in the set $B$. This solution might be not optimal (please see the @j_random_hacker counterexample in comments), and it's unclear how close this solution will be to the optimal one. The time complexity of this algorithm is exponential, cause ...


3

It is common to prove the decidability of first-order Euclidean geometry by encoding the language of Euclidean geometry into the language of real closed fields and then showing that the latter is decidable. A singly-exponential space upper bound on deciding the first-order theory of real closed fields was proven in Ben-Or, Kozen, and Reif (1986). This ...


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. ...


3

Consider 3 additional lines such that their arrangement consists of a single bounded (triangular) cell $C$ and $F \subset C$. Then every edge of $F$ belongs to a zone (using a terminology from your textbook) of at least one of the 3 added lines. And all 3 zones of 3 added lines contain at most $30n$ edges according to Zone Theorem. So $F$ has no more than $...


3

The convex hull of 10 collinear points is the line segment between the two extreme points. No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. . A definition in math, such as the definition of convex hull, is the strictest kind of ...


3

As you have suspected, it is impossible for a simple smooth closed curve to contain the line segment from (−1,0) to (1,0) such that its local feature size at $(0,0)$ is arbitrarily small. On other hand, it is easy to draw a self-intersecting smooth curve with that property. Here is an example. In fact, for every smooth curve that contains the line segment ...


3

The approach in your comment certainly works, and is probably your best bet. If you think of the Platonic solid centred at the origin, then the coordinates of a a point located at the centre of each face is equal (up to normalisation) to those of a vector normal to the face. So you can, in principle, take a point on the sphere, search all the faces and find ...


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/...


2

Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the generators.


2

In "Counting Convex Polygons in Planar Point Sets" (link) Mitchell et al. show an algorithm which can do this in time $O(cn^3)$. Note however that if you need to report those polygons then you can't do better than $O(n^c)$ as there might be $\Omega(n^c)$ such polygons to begin with (consider for example $n$ points in convex position).


2

The following randomized incremental algorithm finds a set of disks, containing all the points from the set $A$ except all the points from the set $B$, in polynomial time. It's unclear, how close this set of disks will be to the optimal solution. The algorithm maintains a disk set, containing a subset of the set $A$ and not containing any points from the ...


2

If you choose a formula with parameter $t$ you'll get the $P_x$ value as a result of a number of operations - additions, multiplications and one division: $$t = \frac{(x_1-x_3)(y_3-y_4)-(y_1-y_3)(x_3-x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}$$ $$P_x = x_1 + t(x_2-x_1)$$ The number $x_2=72057594037954921$ contains 17 significant decimal digits - so it ...


2

The Fréchet distance is a similarity measure for trajectories that often works well for curves that we consider visually similar. However, it is not scale or translation invariant, because it compares the distances between the points of the trajectories. You can try the Direction-Based Fréchet Distance, introduced in this paper by de Berg and Cook. This is ...


2

Note that the statement you want prove is equivalent to showing that the shaded triangles in figure 33.4b are non-empty, or more precisely (for the left triangle) that there exists a vertical line $x$ with x-coordinate strictly less1 than $p$ such that the triangle enclosed by segments $a,b$ and line $x$ does not contain a point of any other segment. To ...


2

Most spatial indexes should be good, especially if your rectangles are axis aligned. Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$. For rectangles, the simplest index is probably a ...


2

Your problem can be solved in linear time. This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question). In ...


2

One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial) Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen ...


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

What is cross product of 2 vectors in ${\rm I\!R^2}$ ? If you compute the crossproduct of 2 vectors on the $xy$ plane you get a vector along the $z$ axis. In 2D the crossproduct is defined as the (scalar) $z$ value of that vector. Moreover the value is positive is the angle goes one way and negative if it goes the other way (which exact way depends on the ...


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 ...


2

In order to get valid paths in the free space from paths in the graph $G=(V,E)$ that is constructed via the trapezoidal decomposition, we require that all edges of $G$ lie inside the free space. The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly ...


2

In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters. Thus, the transformation is uniquely determined if you have two points $p_1,p_2$ from the first set and two points $q_1,q_2$ and if you know that $p_1$ transforms to $q_1$ and $p_2$ to $q_2$. You can find this linear ...


Only top voted, non community-wiki answers of a minimum length are eligible