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

answered Nov 3 '12 at 0:20

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered Jan 3 '18 at 17:55

David E Speyer

124k1010 gold badges313313 silver badges592592 bronze badges

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

answered Aug 30 '12 at 0:28

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered Nov 15 '12 at 1:10

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered Jan 4 '15 at 15:13

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered May 29 '12 at 20:13

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

convex-geometry computational-geometry mg.metric-geometry oc.optimization-and-control locally-convex-spaces

answered Jun 3 '12 at 14:51

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered Sep 14 '14 at 13:41

Joseph O'Rourke

133k2222 gold badges271271 silver badges784784 bronze badges

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

answered Sep 29 '14 at 17:00

David Eppstein

17.3k22 gold badges4646 silver badges107107 bronze badges

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.

answered Sep 8 '16 at 14:42

Anton Petrunin

35.1k55 gold badges9393 silver badges214214 bronze badges

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

#### Related Tags

computational-geometry × 350mg.metric-geometry × 105

discrete-geometry × 71

algorithms × 55

convex-polytopes × 37

ag.algebraic-geometry × 36

reference-request × 32

convex-geometry × 29

co.combinatorics × 28

graph-theory × 24

computational-complexity × 17

polygons × 17

euclidean-geometry × 15

plane-geometry × 15

dg.differential-geometry × 14

polyhedra × 13

polynomials × 12

oc.optimization-and-control × 11

computer-algebra × 11

at.algebraic-topology × 10

linear-programming × 9

pr.probability × 8

linear-algebra × 8

ac.commutative-algebra × 8

na.numerical-analysis × 8