Jump to content

Talk:Distributive polytope

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Convexity

[edit]
Convex hull

I believe the polygon (1,1) / (2,5) / (3,6) / (7,7) / (6,3) / (2,2) / (1,1) satisfies the definition from Felsner.Knauer.2019 (see below); however, as can be seen in the picture, it is not convex.

All connecting lines between any two vertices are visible in the picture (interior connections in light grey), most of them approach their endpoints within the quadrant I or III (light green in the picture), meaning the join of both endpoints equals one of them, and likewise for the meet. There are two exceptions, viz. the line (2,5) to (6,3), and the line (3,6) to (6,3), for which the picture shows (in light red) the rectangles for join and meet construction; both joins and both meets are within the polygon. Thus, at least joins and meets of all vertices are within the polygon.

I guess, by some clever estimation arguments, the same can be shown for all points of the perimeter, and finally for all points of the polygon area.

If I'm right, the restriction to convex polytops should be removed from the article (in fact, I didn't find it in Felsner.Knauer.2011), and the picture might serve to illustrate a simple 2-dimentional example. - Jochen Burghardt (talk) 12:44, 14 November 2019 (UTC)[reply]

Being a better hacker than mathematician, I ran a computer program to check all possibilities, with a resolution of 1 length unit ≅ 100 pixels, and didn't find a violation of the Felsner.Knauer.2019 definition. - Jochen Burghardt (talk) 18:55, 14 November 2019 (UTC)[reply]
Do you have a good, standard, well-accepted definition of polyhedron/polytope that allows nonconvexity and applies in arbitrary dimensions? I don't. Even in three dimensions the definitional issue is a mess; see Polyhedron#Definition. And Theorem 4 of Felsner et al appears to explicitly assume convexity. —David Eppstein (talk) 19:16, 14 November 2019 (UTC)[reply]
I see your point. I didn't dive deep enough into Felsner.Knauer.2019 to understand theorem 4; I had just searched the keyword "convex". I don't have a good general definition of polytope either. (If I were to come up with one, I'd try solutions sets of conjunctions of disjunctions of linear inequations. This would probably admit too many degenerate forms as polytopes, but possibly many of them would be ruled-out by the distributivity condition.) I uploaded a picture of the convex hull of the above polygon; it might serve as an illustration to the article. - Jochen Burghardt (talk) 10:16, 15 November 2019 (UTC)[reply]