33

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online at http://...


29

Seymour and Robertson have indeed said that, and in fact they wrote that in their 2003 article in which they published the graph structure theorem. Here is the quote from Robertson and Seymour „Graph Minors. XVI. Excluding a non-planar graph“ (Journal of Combinatorial Theory, Series B, Vol. 89, Issue 1, Sept. 2003, pages 43–76, doi:10.1016/S0095-8956(03)...


21

The standard simple proof that $\sum_{n=1}^\infty \frac1{n^2}$ converges is to round each $n$ down to the nearest $2^k$; this rounds each $\frac1{n^2}$ up to the nearest $\frac1{2^{2k}}$. In fact, one gets $2^k$ copies of $\frac1{2^{2k}}$ for each $k$; hence $$\sum_{n=1}^\infty n^{-2} < \sum_{k=0}^\infty 2^k\frac1{2^{2k}} = \sum_{k=0}^\infty \frac1{2^{...


18

You will find more information about this in the textbook Modern Computer Algebra by von zur Gathen and Gerhard. I will illustrate my answer using one particular application of this: zero testing of arbitrary expressions. The foundational papers here are Determining equivalence of expressions in random polynomial time by G.H. Gonnet, STOC '84 New results ...


16

I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:              This is well-understood & explored algorithmically, but nevertheless a very delicate computation, as the term regularized indicates. You are ...


15

Note: This answer is wrong. There are two problems: The claim of Lemma 1 should presumably be read in the context of the global assumption in Paulhus's paper that $w\leq l$. This assumption invalidates the instance I wanted to use (i.e. $l=\frac12$, $w=1$). The proof of the lemma seems flawed, as mentioned below and succinctly summarised in Yoav Kallus’s ...


15

No, these are all. The edge graph of the octahedron has no $K_4$ subgraph, so you have to add a new edge to make a triangulation. The only possible places for a new edge are connecting opposite vertices. You can only add one such edge, as any two meet in their interior. So every triangulation of the octahedron (without new vertices) adds exactly one of the ...


14

The problem is NP hard. Here is a proof sketch. The problem is to determine if there is a point $y$ with $\|y\|=1$ outside of the convex hull of given points $x_1,\dots, x_n$. Note that such point exists if and only if there is hyperplane at distance less than $1$ from the origin such that all points $x_1, \dots, x_n$ and $0$ lie on one side of the ...


14

The answer to 1 is no. To see this, note that every edge-crossing graph is a string graph. A string graph is a graph which is the intersection graph of arbitrary curves in the plane. However, there are graphs which are not even string graphs. One example of a graph which is not a string graph is $K_5$ with each edge subdivided once. To see this, let $...


13

Let $P$ be your polygon, $e$ an edge of $P$. I will interpret one aspect of your question as seeking all the maximal rectangles with one side flush with each $e$, each rectangle $R$ maximal in the sense that (a) $R \subset P$ but (b) there is no other rectangle $R' \subset P$ with $R' \supset R$. If you can solve this for one edge $e$, you can iterate ...


13

The problem you identify is called the facet enumeration problem in the literature: Given the vertices, find a description of the facets. There has been quite a bit of work on this. For $n$ points in $d$ dimensions, $O(n^{\lfloor d/2 \rfloor})$ is achievable, and aymptotically worstcase optimal. But this is a theoretical result. The work of Avis & ...


13

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard: Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23.1 (2000): 73-110. (Journal link.)           Approximation algorithms have ...


11

The integral essentially asks for the probability that, for $n$ independent "events" uniformly distributed in $[0,1]$, at least one happens after $c_n$, at least two happen after $c_{n-1}$, etc (thinking of the unit interval as time). Let $P_n(c_1,\dots,c_n) = n!\cdot J$ denote this probability (the integral $J$ also requires the $n$ events to occur in a ...


11

Define a mean algebra to be a set $S$ with an binary operation $M$ satisfying (1), (2), and (4). We can define $M(a,b,c,d)=M(M(a,b),M(c,d))$ and this will depend only on the multiset $\{a,b,c,d\}$. More generally, we can think of $M$ as an operation defined on multisets of size $2^n$ for any $n>0$ (and this is well-defined by an easy induction on $n$ ...


10

Let me answer at least some of your questions. I will only talk about your first definition of the cells, since these are somewhat nicer, as Igor Rivin pointed out. You consider the function $f(w_1)=w_1\cdot\text{Area}(w_1)$ and asked whether it is convex. I assume you mean "Is the set $\{(x,f(x)):f(x)\geq 0\}\subset\mathbb{R}^2$ convex?", or in other words:...


10

I believe the answer is (in general) No for the following reason. A configuration of points in $\mathbb{P}^2$ is projectively dual to an arrangement of lines in $\mathbb{P}^2$. The question you ask, translated to arrangements of lines, is whether an arrangement can always be continuously moved to any isomorphic arrangement, all the while remaining ...


10

Here is an argument that Béla Bollobás showed me once. (this was motivated by a physics paper where a simulation was done showing that the average number of edges per face was 5.997$\pm$ 0.005). Take a large number of seeds (i.e. points generating the Voronoi diagram) and make the assumption that there are no multiple points: points of that are ...


10

For your first question, Mader proved that all $K_6$-minor-free graphs (which includes all linklessly embeddable graphs) on $n$ vertices have at most $4n-10$ edges (thanks to David Eppstein for the reference). The answer to your second question is no. This follows because Apex graphs are linklessly embeddable, and one easily checks that they do not have ...


10

cddlib is rather old; a much more efficient implementation of the double description method is in PPL (Parma Polyhedra Library). One frontend to PPL can be found in Sagemath: http://www.sagemath.org/doc/reference/geometry/sage/geometry/polyhedron/constructor.html PPL will perform computations exactly. Apart from the double description there is the reverse ...


10

Let $a,b,c\in\mathbb{O}$ be octonions and consider the linear map $L:\mathbb{O}\to\mathbb{O}$ defined by $$ L(x) = (b(cx))a = R_aL_bL_c(x). $$ One desires a formula for the characteristic polynomial of $S$, the symmetric part of $L$, i.e., $$ S(x) = \tfrac12\bigl(R_aL_bL_c + {}^t(R_aL_bL_c) \bigr). $$ (I note that the OP seems to have inadvertently omitted ...


9

I believe you are looking for the radius of a largest empty ball among your point set, a quantity which goes under the name of dispersion. This plays a role in robotics algorithms, e.g., LaValle's book. Here is a survey which might lead to other relevant references: G. Rote , R.F. Tichy, "Quasi-Monte-Carlo methods and the dispersion of point sequences," ...


9

Yeah, there is a shear transformation that takes one of the ellipses to a circle. The least area ellipse enclosing the resulting figure is now evident by symmetry. Then use the inverse of the shear. Now that I think of it, you can just shrink along the major axis of one of the ellipses and expand on the minor axis to get the circle. All manipulations ...


9

Take your linear program and add the objective function max $x$, and the inequalities $\lambda_i - x \geq 0$. If the point is on the exterior, the optimum solution has $x=0$. Otherwise, there is a solution with $x > 0$.


9

The number of $(d{-}1)$-facets of a Poisson-process Voronoi cell in $\mathbb{R}^d$ is: $6$ for $d{=}2$; $\approx 15.5$ for $d{=}3$; and $\approx 37.8$ for $d{=}4$. For references and other stats, see: Masaharu Tanemura, "Random Voronoi Cells of Higher Dimensions." (link). Here is an unrelated but attractive image from www.qhull.org:     ...


8

There are two ways to interpret your question. First -- since you are talking about braids, perhaps you are asking about the conjugacy problem for braids. This is the same as taking a braid closure, with an braid axis. In this case the ultra summit set (USS) of a braid $\sigma$ is a complete invariant for conjugacy classes. It is an open question ...


8

The expected number of sides and size of a typical cell (typical is interpreted in the sense of Palm measures which basically means what you see on average in a large ball) for the Voronoi cells of a Poisson process with constant intensity in the Euclidean plane (as well as higher dimensional Euclidean spaces) are known. See for example the book by Moller "...


8

The reference given in the Wikipedia article on linkless embedding for the $4n-10$ bound on the number of edges in a linkless embeddable graph is Mader, W. (1968), "Homomorphiesätze für Graphen", Mathematische Annalen 178 (2): 154–168, doi:10.1007/BF01350657. Apparently Mader proves this bound more generally for $K_6$-minor-free graphs. As the Wikipedia ...


8

There is an exponential upper bound of $9^n$, since every vertex of $B_1 \cap B_2$ is the intersection of a $k$-face of $B_1$ and a $(n-k)$-face of $B_2$ for some $k$, and the $\ell_1$-ball has $3^n$ faces (all dimensions counted together). You cannot do better for large $n$ except for the value of the constant $9$. Indeed, let $B_1$ be $\ell_1$ ball of ...


8

For topological combinatorics, Voronoi diagrams provide extremely nice configuration spaces. In particular, some mass partitioning problems can be tackled using this type of subdivision. Power diagrams (which extend Voronoi diagrams) are more commonly used for this purpose. See for instance the expository article of Günter Ziegler [1] where he explains ...


8

This is a standard question. Look at the following image from Morgan's "Geometric measure theory". It should convince you that the answer is no. The curve admits two area minimizing discs and it admits arbitrary small perturbations so that just one of them stay area minimizing.


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