src/HOL/Analysis/Polytope.thy
changeset 80914 d97fdabd9e2b
parent 78656 4da1e18a9633
equal deleted inserted replaced
80913:46f59511b7bb 80914:d97fdabd9e2b
     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>