40

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

30

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

24

Take a very obtuse isosceles triangle and chop its acute angles.

answered Apr 25 '21 at 1:11

Anton Petrunin

37.3k66 gold badges107107 silver badges232232 bronze badges

23

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

23

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

15

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

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

135k1313 gold badges356356 silver badges662662 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

142k2828 gold badges304304 silver badges854854 bronze badges

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

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

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

142k2828 gold badges304304 silver badges854854 bronze badges

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

answered Jun 16 '20 at 11:34

Robert Bryant

95.3k88 gold badges291291 silver badges398398 bronze badges

9

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

9

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

9

The source info (War in the Age of Intelligent Machines) identifies the fractal as a Julia set, iterates of $z\mapsto z^2+z_0$. It has evidently been distorted (warped) to give it a 3D appearance. I played around with a spiral-shaped Julia set I found at pixels.com and could create an image such as this.
The Mathematica command
Manipulate[JuliaSetPlot[a- b*...

answered Sep 7 '20 at 16:37

Carlo Beenakker

139k1212 gold badges334334 silver badges482482 bronze badges

9

Indeed that paper I cited in the comments describes how to determine all
symmetries of a polygon $P$ in $O(n)$ time.
The polygon is first translated so that its centroid is at the origin.
Then a "representation" $L(P)$ of $P$ is constructed.
$L$ is an $n$-tuple of pairs $(d_i,\alpha_i)$, where $d_i$ is the length
of polygon edge $i$, and $\alpha_i =...

answered Mar 25 '21 at 13:36

Joseph O'Rourke

142k2828 gold badges304304 silver badges854854 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 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

No, and you can see this from just a counting argument.
For determining which of the $ n $ chords of the circle intersect, it is enough to know the order of the $ 2n $ endpoints on the circle. (You can assume that no two endpoints coincide.) There are at most $ (2n)!/2^n $ such orders (the two endpoints of a chord aren't distinguishable). On the other ...

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

37.3k66 gold badges107107 silver badges232232 bronze badges

8

Try SageManifolds http://sagemanifolds.obspm.fr/
See this example (there are several others) for how to compute the curvature tensor from the metric
http://nbviewer.jupyter.org/github/sagemanifolds/SageManifolds/blob/master/Worksheets/v1.0/SM_Schwarzschild.ipynb
Hint: it's just
R = g.riemann()
R.display()
EDIT: Here's a complete example
You can open ...

8

It depends very much on the type of simplicial complex you're using. If you have points in 3d then doing Cech/Delaunay complex is feasible with millions of points. If you have high dimensional data, complexes will generally blow up in size and millions of points will be too much. Finding ways to decrease the size of complexes, possibly using approximations (...

at.algebraic-topology computational-geometry data-analysis computational-topology persistent-homology

7

There are several possible ways to interpret your question. Let me mention three, all very different:
(1) For general graphs, say you want to decide if there is such realization at all, and if yes find it approximately. This is called Graph Realization Problem and it is well studied both theoretically and practically (e.g. it is easily NP-hard). For ...

7

This is equivalent to sphere packing in a cube. This type of problem is messy. Even if you look at circle packings in a square, only a few configurations have been proved optimal. The best configurations known for many other values are complicated, and it's not easy to specify a short list of possible combinatorial types of configurations to test.
Hugo ...

7

Perhaps search from this first paper, which presents "a concise review of advances ... on planar Poisson-Voronoi tesselations":
Hilhorsta, H. J. "Statistical properties of planar Voronoi tessellations." The European Physical Journal B-Condensed Matter and Complex Systems 64.3 (2008): 437-441.
(journal link)
...

answered Sep 15 '14 at 11:49

Joseph O'Rourke

142k2828 gold badges304304 silver badges854854 bronze badges

7

There are certainly many "digital artists" who are inspired
by topology in their 3D-print designs. E.g., Torolf Sauermann:
(Image from this web site.)

answered Jan 21 '15 at 17:50

Joseph O'Rourke

142k2828 gold badges304304 silver badges854854 bronze badges

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

#### Related Tags

computational-geometry × 392mg.metric-geometry × 129

discrete-geometry × 93

algorithms × 59

convex-polytopes × 41

ag.algebraic-geometry × 39

convex-geometry × 39

reference-request × 33

co.combinatorics × 28

graph-theory × 26

plane-geometry × 22

polygons × 20

computational-complexity × 18

dg.differential-geometry × 16

euclidean-geometry × 15

oc.optimization-and-control × 13

computer-algebra × 13

polyhedra × 13

polynomials × 12

at.algebraic-topology × 10

linear-algebra × 10

linear-programming × 10

triangulations × 10

pr.probability × 9

ac.commutative-algebra × 9