equal
deleted
inserted
replaced
6 imports Cartesian_Euclidean_Space Path_Connected |
6 imports Cartesian_Euclidean_Space Path_Connected |
7 begin |
7 begin |
8 |
8 |
9 subsection \<open>Faces of a (usually convex) set\<close> |
9 subsection \<open>Faces of a (usually convex) set\<close> |
10 |
10 |
11 definition\<^marker>\<open>tag important\<close> face_of :: "['a::real_vector set, 'a set] \<Rightarrow> bool" (infixr "(face'_of)" 50) |
11 definition\<^marker>\<open>tag important\<close> face_of :: "['a::real_vector set, 'a set] \<Rightarrow> bool" (infixr \<open>(face'_of)\<close> 50) |
12 where |
12 where |
13 "T face_of S \<longleftrightarrow> |
13 "T face_of S \<longleftrightarrow> |
14 T \<subseteq> S \<and> convex T \<and> |
14 T \<subseteq> S \<and> convex T \<and> |
15 (\<forall>a \<in> S. \<forall>b \<in> S. \<forall>x \<in> T. x \<in> open_segment a b \<longrightarrow> a \<in> T \<and> b \<in> T)" |
15 (\<forall>a \<in> S. \<forall>b \<in> S. \<forall>x \<in> T. x \<in> open_segment a b \<longrightarrow> a \<in> T \<and> b \<in> T)" |
16 |
16 |
652 subsection\<open>Exposed faces\<close> |
652 subsection\<open>Exposed faces\<close> |
653 |
653 |
654 text\<open>That is, faces that are intersection with supporting hyperplane\<close> |
654 text\<open>That is, faces that are intersection with supporting hyperplane\<close> |
655 |
655 |
656 definition\<^marker>\<open>tag important\<close> exposed_face_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" |
656 definition\<^marker>\<open>tag important\<close> exposed_face_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" |
657 (infixr "(exposed'_face'_of)" 50) |
657 (infixr \<open>(exposed'_face'_of)\<close> 50) |
658 where "T exposed_face_of S \<longleftrightarrow> |
658 where "T exposed_face_of S \<longleftrightarrow> |
659 T face_of S \<and> (\<exists>a b. S \<subseteq> {x. a \<bullet> x \<le> b} \<and> T = S \<inter> {x. a \<bullet> x = b})" |
659 T face_of S \<and> (\<exists>a b. S \<subseteq> {x. a \<bullet> x \<le> b} \<and> T = S \<inter> {x. a \<bullet> x = b})" |
660 |
660 |
661 lemma empty_exposed_face_of [iff]: "{} exposed_face_of S" |
661 lemma empty_exposed_face_of [iff]: "{} exposed_face_of S" |
662 proof - |
662 proof - |
871 qed |
871 qed |
872 |
872 |
873 subsection\<open>Extreme points of a set: its singleton faces\<close> |
873 subsection\<open>Extreme points of a set: its singleton faces\<close> |
874 |
874 |
875 definition\<^marker>\<open>tag important\<close> extreme_point_of :: "['a::real_vector, 'a set] \<Rightarrow> bool" |
875 definition\<^marker>\<open>tag important\<close> extreme_point_of :: "['a::real_vector, 'a set] \<Rightarrow> bool" |
876 (infixr "(extreme'_point'_of)" 50) |
876 (infixr \<open>(extreme'_point'_of)\<close> 50) |
877 where "x extreme_point_of S \<longleftrightarrow> |
877 where "x extreme_point_of S \<longleftrightarrow> |
878 x \<in> S \<and> (\<forall>a \<in> S. \<forall>b \<in> S. x \<notin> open_segment a b)" |
878 x \<in> S \<and> (\<forall>a \<in> S. \<forall>b \<in> S. x \<notin> open_segment a b)" |
879 |
879 |
880 lemma extreme_point_of_stillconvex: |
880 lemma extreme_point_of_stillconvex: |
881 "convex S \<Longrightarrow> (x extreme_point_of S \<longleftrightarrow> x \<in> S \<and> convex(S - {x}))" |
881 "convex S \<Longrightarrow> (x extreme_point_of S \<longleftrightarrow> x \<in> S \<and> convex(S - {x}))" |
977 qed |
977 qed |
978 |
978 |
979 subsection\<open>Facets\<close> |
979 subsection\<open>Facets\<close> |
980 |
980 |
981 definition\<^marker>\<open>tag important\<close> facet_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" |
981 definition\<^marker>\<open>tag important\<close> facet_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" |
982 (infixr "(facet'_of)" 50) |
982 (infixr \<open>(facet'_of)\<close> 50) |
983 where "F facet_of S \<longleftrightarrow> F face_of S \<and> F \<noteq> {} \<and> aff_dim F = aff_dim S - 1" |
983 where "F facet_of S \<longleftrightarrow> F face_of S \<and> F \<noteq> {} \<and> aff_dim F = aff_dim S - 1" |
984 |
984 |
985 lemma facet_of_empty [simp]: "\<not> S facet_of {}" |
985 lemma facet_of_empty [simp]: "\<not> S facet_of {}" |
986 by (simp add: facet_of_def) |
986 by (simp add: facet_of_def) |
987 |
987 |
1022 "F facet_of {x. a \<bullet> x \<ge> b} \<longleftrightarrow> a \<noteq> 0 \<and> F = {x. a \<bullet> x = b}" |
1022 "F facet_of {x. a \<bullet> x \<ge> b} \<longleftrightarrow> a \<noteq> 0 \<and> F = {x. a \<bullet> x = b}" |
1023 using facet_of_halfspace_le [of F "-a" "-b"] by simp |
1023 using facet_of_halfspace_le [of F "-a" "-b"] by simp |
1024 |
1024 |
1025 subsection \<open>Edges: faces of affine dimension 1\<close> (*FIXME too small subsection, rearrange? *) |
1025 subsection \<open>Edges: faces of affine dimension 1\<close> (*FIXME too small subsection, rearrange? *) |
1026 |
1026 |
1027 definition\<^marker>\<open>tag important\<close> edge_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" (infixr "(edge'_of)" 50) |
1027 definition\<^marker>\<open>tag important\<close> edge_of :: "['a::euclidean_space set, 'a set] \<Rightarrow> bool" (infixr \<open>(edge'_of)\<close> 50) |
1028 where "e edge_of S \<longleftrightarrow> e face_of S \<and> aff_dim e = 1" |
1028 where "e edge_of S \<longleftrightarrow> e face_of S \<and> aff_dim e = 1" |
1029 |
1029 |
1030 lemma edge_of_imp_subset: |
1030 lemma edge_of_imp_subset: |
1031 "S edge_of T \<Longrightarrow> S \<subseteq> T" |
1031 "S edge_of T \<Longrightarrow> S \<subseteq> T" |
1032 by (simp add: edge_of_def face_of_imp_subset) |
1032 by (simp add: edge_of_def face_of_imp_subset) |
2982 |
2982 |
2983 subsection\<open>Simplexes\<close> |
2983 subsection\<open>Simplexes\<close> |
2984 |
2984 |
2985 text\<open>The notion of n-simplex for integer \<^term>\<open>n \<ge> -1\<close>\<close> |
2985 text\<open>The notion of n-simplex for integer \<^term>\<open>n \<ge> -1\<close>\<close> |
2986 |
2986 |
2987 definition\<^marker>\<open>tag important\<close> simplex :: "int \<Rightarrow> 'a::euclidean_space set \<Rightarrow> bool" (infix "simplex" 50) |
2987 definition\<^marker>\<open>tag important\<close> simplex :: "int \<Rightarrow> 'a::euclidean_space set \<Rightarrow> bool" (infix \<open>simplex\<close> 50) |
2988 where "n simplex S \<equiv> \<exists>C. \<not> affine_dependent C \<and> int(card C) = n + 1 \<and> S = convex hull C" |
2988 where "n simplex S \<equiv> \<exists>C. \<not> affine_dependent C \<and> int(card C) = n + 1 \<and> S = convex hull C" |
2989 |
2989 |
2990 lemma simplex: |
2990 lemma simplex: |
2991 "n simplex S \<longleftrightarrow> (\<exists>C. finite C \<and> |
2991 "n simplex S \<longleftrightarrow> (\<exists>C. finite C \<and> |
2992 \<not> affine_dependent C \<and> |
2992 \<not> affine_dependent C \<and> |