Extremal Problems for Geometric Hypergraphs

of 12

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
12 pages
0 downs
2 views
Share
Description
Extremal Problems for Geometric Hypergraphs
Transcript
  ExtremalProblemsforGeometricHypergraphs  1  ExtremalProblemsforGeometricHypergraphs  TamalK.Dey  1  andJ anosPach  2  Abstract  A  geometrichypergraph  H  isacollectionof  i  -dimensionalsimplices,called  hyperedges  or,simply, edges  ,inducedbysome(  i  +1)-tuplesofa  vertexset  V  ingeneralpositionin  d  -space.The topologicalstructureofgeometric  graphs  ,i.e.,thecase  d  =2  ;i  =1,hasbeenstudiedextensively,anditprovedtobeinstrumentalforthesolutionofawiderangeofproblemsincombinatorialand computationalgeometry.Theyincludethe  k  -setproblem,proximityquestions,boundingthenum- berofincidencesbetweenpointsandlines,designingvariousecientgraphdrawingalgorithms,etc.Inthispaper,wemakeanattempttogeneralizesomeofthesetoolstohigherdimensions.Wewillmainlyconsiderextremalproblemsofthefollowingtype.Whatisthelargestnumberof edges(  i  -simplices)thatageometrichypergraphof  n  verticescanhavewithoutcontainingcertain  forbidden  congurations?Inparticular,wediscussthespecialcaseswhentheforbiddencongura- tionsare  k  intersectingedges, k  pairwiseintersectingedges, k  crossingedges, k  pairwisecrossing edges, k  edgesthatcanbestabbedbyan  i  -at,etc.Someofourestimateswillbetight. 1Introduction  Inrecentyears,thestudyofgraphdrawingshasbecomearichseparatedisciplinewithincomputational geometry.Muchoftheresearchhasbeenmotivatedbyapplications,includingsoftwareengineering, CAD,databasedesign,cartography,circuitschematics,automaticanimation,visualinterfaces,etc. (See27].)Itisquiteremarkablethatclassicalgraphtheoryprovedtoberatherpowerlesstotackle manyofthearisingproblems.Instead,oneoftenhadtodevelopnewtopologicaltoolstodealwith familiesofcurves,i.e.,graphsdrawnintheplaneorinsomeothersurfaces.Perhapsthebestknown exampleistheLipton{TarjanSeparatorTheoremforplanargraphs15],whichhasmanyextensions, generalizations,andabroadspectrumofapplicationsrangingfromnumericalanalysistocomplexity theory.Inparticular,itenablesustousethedivide-and-conquerparadigmtoconstructvarious geometricrepresentationsofabstractgraphsandnetworks.Anotherimportantexampleisthefollowing resultdiscoveredindependentlybyAjtai-Chv atal-Newborn-SzemerediandLeighton.Itcanbeused toobtaine.g.sharpboundsforthearearequirementofgraphlayouts.Let    (  G  )denotethe  crossing number  ofagraph  G  ,i.e.,theminimumnumberofcrossingpairsofedgesoverallplanardrawingsof  G  .  1  Dept.ofCSE,IIT,Kharagpur,India721302  2  MathematicalInstituteoftheHungarianAcademyofSciencesandCourantInstituteofMathematicalSciences,New YorkUniversity,NewYork,NY10012.ResearchsupportedbyNSFgrantCCR-94-24398,PSC-CUNYResearchAward 663472,andOTKA-4269.  ExtremalProblemsforGeometricHypergraphs  2  Theorem1.1  114Let  G  beasimplegraphwith  n  verticesand  e  (  G  )  edgesIf  e  (  G  )    4  n  then    (  G  )    e  (  G  )  3  100  n  2  AsSzekely24]pointedout,thisresultalmostimmediatelyimpliestheSzemeredi-Trottertheorem 25],26]onthenumberofincidencesbetweenpointsandlines.Hisargumentissoniceandshort thatwecannotresistadaptingittoestablishthefollowinggeneralizationoftheSzemeredi-Trotterthe- orem,whichwasfoundbyClarkson-Edelsbrunner-Guibas-Sharir-Welzlandhasnumerousalgorithmic consequences.(ForsomeotherapplicationsofSzekely'sidea,see19].)  Theorem1.2  8Thetotalnumberofsidesof  n  distinctcellsdeterminedby  m  linesingeneral positionintheplaneisatmost  O  (  m  2  =  3  n  2  =  3  +  m  )  Proof.  Noticethatitissucienttoprovetheassertionforasystemofcells  C  ,notwoofwhichshare anedge.Pickapoint  p  i  ineachcell  c  i  2C  .Foranypair(  s  i  ;s  j  )ofcollinearedgesbelongingto  c  i  2C  and  c  j  2C  ,respectively,connect  p  i  to  p  j  byapolygonalchainoflengththreeviathemidpointsof thesegments  s  i  and  s  j  ,providedthatthispolygonisnotadjacenttoanyothermemberof  C  .The collectionofthesepolygonalchainscanberegardedastheedgesetofagraph  G  0  whosevertices are  p  1  ;:::;p  n  .Ifalineisadjacentto  k  cellsin  C  ,thenitcontributestoexactly  k  ?  1edgesof  G  0  . Hence,  X  ,thetotalnumberofsidesofallcellsin  C  ,diersfromthenumberofedgesof  G  0  byatmost  m  .Removingthemultipleedgesfrom  G  0  ,weobtainasimplegraphwhosenumberofedgessatises  e  (  G  )    e  (  G  0  )  =  4    (  X  ?  m  )  =  4.Inviewofthefactthatanycrossingbetweentwoedgesof  G  occursat acrossingofsomepairoflinesofthearrangement,Theorem1.1impliesthateither  e  (  G  )  <  4  n  or    m  2  !      (  G  )    e  (  G  )  3  100  n  2  :  Since  X    4  e  (  G  )+  m  ,Theorem1.2follows. Givenasetof  n  pointsingeneralpositionintheplane,jointwoofthembyalinesegmentif thereareexactly  k  pointsononesideofthelineconnectingthem.Let  G  denotetheresultinggraph. Lov asz16]provedthatnostraightlinecancrossmorethan2  k  edgesof  G  .NowTheorem1.1implies thatthenumberofedges(thenumberofsocalled  k  sets  )isatmost  O  (  k  1  =  2  n  ).Indeed,ifthenumber ofedgesis  e  ,theneitherwehave  e<  4  n  orthereexistsanedgecrossingatleast  e  2  =  (50  n  2  )other edges.Thus,  e  2  =  (50  n  2  )    2  k  ,asrequired.(See21]foraslightimprovement.)Itwasshownby B ar any-F uredi-Lov asz6]thatasimilarapproachcanbeusedtoestablishanon-trivialupperbound  onthenumberof  halvingplanes  in3-space,whichwassubsequentlyimprovedto  O  (  n  8  =  3  )in4],10]. Agraphdrawnintheplanebypossiblycrossingstraight-linesegmentsiscalleda  geometricgraph  . Moreprecisely,ageometricgraph  G  consistsofasetofpoints  V  ingeneralpositionintheplane andasetofsegments  E  whoseendpointsbelongto  V  .Aswasdemonstratedabove,foranumberof applicationsitwasnecessarytosolvesomeextremalproblemsforgeometricgraphs.Thesystematic studyoftheseproblemswasinitiatedbyP.Erd} os,Y.Kupitz13],andM.Perles.(Forarecentsurvey, see18].) Itseemsplausiblethattoextendtheincidenceresultstohigherdimensions,toimprovetheupper boundforthenumberoftimestheunitdistancecanoccuramong  n  pointsin3-space,ortomake furtherprogressconcerningthe  k  -setproblem,onehastondtherightgeneralizationsofTheorem 1.1tosystemsofsurfacesorsurfacepatchesin  d  -space.Forsimplicity,wewillonlydiscussthecase whenthesesurfacepatchesareat(simplices).   ExtremalProblemsforGeometricHypergraphs  3  Denition1.1  A  d  -dimensionalgeometric  r  -hypergraph  H  d r  isapair  (  V;E  )  where  V  isasetof pointsingeneralpositionin  <  d  and  E  isasetofclosed  (  r  ?  1)  dimensionalsimplicesinducedby some  r  tuplesof  V  Thesets  V  and  E  arecalledthe  vertexset  and  edgeset  of  H  d r  respectively  Someearlyresultsforcompletegeometrichypergraphs  H  d d  +1  wereestablishedin5],7].Akiyama andAlon3]provedthefollowingtheorem.Let  V  =  V  1    :::    V  d  (  j V  1  j =  :::  =  j V  d  j =  n  )bea  dn  -elementsetingeneralpositionin  <  d  ,andlet  E  consistofall(  d  ?  1)-dimensionalsimpliceshaving exactlyonevertexineach  V  i  .Then  E  contains  n  disjointsimplices.Combiningthiswitharesultof Erd} os11],weobtainanon-trivialupperboundforthenumberofedgesofa  d  -dimensionalgeometric  d  -hypergraphof  n  verticesthatcontainsno  k  pairwisedisjointedges. Ifwewanttoexclude  crossings  ratherthandisjointedges,orwanttogeneralizeTheorem1.1to geometrichypergraphs,wefacethefollowingproblem.Evenifwerestrictourattentiontosystems oftrianglesinducedby3-dimensionalpointsetsingeneralposition,itisnotcompletelyclearhowa \crossing"shouldbedened,letalonethenotionof\crossingnumber".Iftwosegmentscross,they donotshareanendpoint.Shouldthisremaintruefortriangles?Wehavetoclarifytheterminology.  Denition1.2  Twosimplicesaresaidtohavea  non-trivialintersection  iftheirrelativeinteriors haveapointincommonIfinadditionthetwosimplicesarevertexdisjointthentheyaresaidto  cross  Moregenerally  k  simplicesaresaidtohavea  non-trivialintersection  iftheirrelativeinteriors haveapointincommonIfinadditionallsimplicesarevertexdisjointthentheyaresaidto  cross Consider  k  simplices.Itisimportanttonotethatthefactthat  everypair  ofthemhasanon-trivial intersectiondoesnotimplythat  all  ofthemdo.Toemphasizethatthisstrongerconditionissatised, weoftensaythatthesimpliceshavea  nontrivialintersectioninthestrongsense  ,orsimplythatthey  stronglyintersect  .Similarly,asetof  pairwise  crossingsimplicesisnotnecessarily  crossing  .Ifwant toemphasizethatthey  all  cross,wewillsaythatthey  crossinthestrongsense  ,orshortlythatthey  stronglycross  . Aswepickmoreandmoredistinct(  r  ?  1)-dimensionalsimplicesinducedbyasetof  n  points in  <  d  ,thenumberofcrossingsbetweenthemwillusuallyincrease.Theaimofthispaperisto generalizetheplanarresultstoobtainsomeinformationaboutthegrowthrateofthisprocess.Inthe inverseformulation,onecanaskforthemaximumnumberofedgesthata  d  -dimensionalgeometric  r  -hypergraph  H  d r  of  n  verticescanhavewithoutcontainingsomexedcrossingpattern.Throughout thispaper,let  f  d r  (  F  ;n  )denotethismaximum,where  F  isthefamilyof   forbidden  congurations,i.e., forbiddengeometricsubhypergraphs.Mostofourboundswillbeasymptotic:  d  and  r  arethoughtto bexed,while  n  tendstoinnity. Inthenexttwosections,weestimate  f  d r  (  F  ;n  )forvariousfamilies  F  .InSection4,wegeneralize Theorem1.1.Finally,wediscusssomerelatedquestionsandgiveafewapplicationsofourresults.  2Fulldimensionalsimplices  Let  I  r k  (resp.  SI  r k  )denotetheclassofallgeometrichypergraphsconsistingof  k  (  r  ?  1)-dimensional simplices,anytwoofwhichhaveanon-trivialintersection(resp.allofwhicharestronglyintersecting). Similarly,let  C  r k  (resp.  SC  r k  )denotetheclassofallgeometrichypergraphsconsistingof  k  pairwise crossing(resp.stronglycrossing)(  r  ?  1)-simplices.   ExtremalProblemsforGeometricHypergraphs  4  Theorem2.1  Foranyxed  k>  1  onecanselectatmost  O  (  n  d  d=  2  e  )  d  dimensionalsimplicesinduced by  n  pointsin  d  spacewiththepropertythatno  k  ofthemshareacommoninteriorpointThisbound cannotbeimprovedThatis  f  d d  +1  (  I  d  +1  k  ;n  )=(  n  d  d=  2  e  )  ;f  d d  +1  (  SI  d  +1  k  ;n  )=(  n  d  d=  2  e  )  :  Proof.  Clearly,wehave (  n  d  d=  2  e  )    f  d d  +1  (  I  d  +1  k  ;n  )    f  d d  +1  (  SI  d  +1  k  ;n  )  ;  wheretherstinequalityfollowsfromthefactthattherearetriangulationsofsize(  n  d  d=  2  e  )with  n  verticesin  <  d  .Considere.g.theverticalprojectionofthelowerpartofanycyclicpolytopeof  n  verticesin  <  d  +1  . Toseethat  f  d d  +1  (  SI  d  +1  k  ;n  )    O  (  n  d  d=  2  e  ),wesetupachargingscheme.Letusregard  <  d  ?  1  asthe coordinatehyperplanein  <  d  spannedbytherst  d  ?  1axes,andlet  X  d  denotethelastcoordinate axis.Supposethat  X  d  isvertical.Fixageometrichypergraph  H  d d  +1  =(  V;E  )whichhasno  k  edges withacommoninteriorpointandwhose  n  verticesareingeneralposition.Forany  `  -dimensional simplexinducedby  V  ,where  `  b  (  d  ?  1)  =  2  c  ,let  E      E  denotethesetofalledgesof  H  d d  +1  that containontheirboundaries.Itfollowsfromtheconditionon  H  d d  +1  thattheinniteverticalcylinder +  X  d  basedonintersectsatmost2(  k  ?  1)elementsof  E    .Letuschargeoneunitforeach oftheseedges.Sincethetotalnumberof  `  -simpliceswith  `  b  (  d  ?  1)  =  2  c  isatmost  d  d=  2  e  n  d  d=  2  e  , itremainstoshowthateveryedge  e  2  E  hasbeenchargedfor.Indeed,byRadon'stheorem23], thevertexsetoftheorthogonalprojectionof  e  into  <  d  ?  1  canbepartitionedintotwoparts,  S  1  and  S  2  ,suchthattheirconvexhullscrosseachotherand  j S  1  j +  j S  2  j =  d  +1.Supposewithoutlossof generalitythat  j S  1  jb  (  d  +1)  =  2  c  .Thentheconvexhullof  S  1  isan  `  -dimensionalsimplex  1  forsome  `  b  (  d  ?  1)  =  2  c  ,andwehadtocharge  1  for  e  .  Theorem2.2  Let  E  beanysetof  d  dimensionalsimplicesinducedbyan  n  elementpointset  V  <  d  If  E  hasnotwocrossingelementsthen  j E  j =  O  (  n  d  )  andthisboundisasymptoticallytightIn notation  f  d d  +1  (  C  d  +1 2  ;n  )=(  n  d  )  :  Proof.  Toprovethelowerbound,considerageometrichypergraphconsistingofall  d  -dimensional simplicesinducedby  V  thatcontainagivenvertex  v  2  V  . Nextweestablishtheupperbound.If  E  hasnotwosimpliceshavinganon-trivialintersection, then  j E  j  O  (  n  d  d=  2  e  ),bytheprevioustheorem.Otherwise,choosetwo  d  -simplices  1  ;    2  2  E  whose intersectionisnon-trivial.Itiseasytoshow(seee.g.9],10])thatthereexistan  `  1  -face  0  1  of  1  andan  `  2  -face  0  2  of  2  with  `  1  +  `  2  =  d  suchthat  0  1  and  0  2  arecrossing. Assumerstthatthereisanedge  e  2  E  whichisvertexdisjointfrom  0  1  andcontains  0  2  asa face.Theneveryedge  f  2  E  thatcontains  0  1  asafacemustshareatleastonevertexwith  e  .The numberofsuchsimplices  f  isatmost(  d  +1)  ?  n d  ?  `  1  ?  1    .Letusremoveallofthemfrom  E  . Inthesecondcase,everyedge  e  2  E  thatcontains  0  2  asafacesharesavertexwith  0  1  .Obviously, thenumberofsuchsimplices  e  isatmost(  `  1  +1)  ?  n d  ?  `  2  ?  1    .Removeallofthemfrom  E  .   ExtremalProblemsforGeometricHypergraphs  5 Wecontinuethisprocedureuntilthereremainnonon-trivialintersectionsin  E  .Atthispoint,  E  hasatmost  O  (  n  d  d=  2  e  )elements,andthetotalnumberofsimplicesthathavebeenremovedisatmost    n `  1  +1  !  (  d  +1)    n d  ?  `  1  ?  1  !  +    n `  2  +1  !  (  `  1  +1)    n d  ?  `  2  ?  1  !  =  O  (  n  d  )  :  3  (  d  ?  1)  -simplicesin  d  -space  Theorem3.1  Let  E  beafamilyof  (  d  ?  1)  dimensionalsimplicesinducedbyan  n  elementpointset  V  <  d  suchthat  E  hasno  k  memberswithpairwisenontrivialintersections  d;k>  1  Thenfor  k  =2  and  3  wehave  j E  j =  O  (  n  d  ?  1  )  Otherwise  j E  j =  O  (  n  d  ?  1  log  2  k  ?  6  n  )  Innotation  f  d d  (  I  d k  ;n  )=  (  O  (  n  d  ?  1  )  if  k  =2  ;  3  O  (  n  d  ?  1  log  2  k  ?  6  n  )  otherwise Thisresultisasymptoticallytightif  d;k    3  Proof.  For  d  =2,theassertionistrue,bytheresultsof20]and2].Assumethat  d    3.For any(  d  ?  3)-simplexinducedby  V  ,let  E    denotethefamilyofallmembersof  E  thatcontain asaface.Pickanypoint  p    intherelativeinteriorof,andlet  F    denotethe3-dimensionalat orthogonaltoandpassingthrough  p    . Every  e  2  E    meets  F    inatriangle,whosetwosidesincidentto  p    aretheintersectionsof  F    withthetwo(  d  ?  2)-facesof  e  containing.Thus,thetotalnumberofsidesincidentto  p    that occurinsome  e  \  F    (  e  2  E    )isatmost  n  ?  d  +2  <n  .Takeasmall2-dimensionalsphere  S  2    F    centeredat  p    .Theintersectionsof  S  2  withtheelementsof  E    formtheedgesetofagraphwithat most  n  vertices.Itfollowsfromthepropertiesof  E  thatthisgraphhasno  k  pairwisecrossingedges, so,bytheplanarresults,itsnumberofedges,  j E    j ,satises  j E    j =  (  O  (  n  )if  k  =2  ;  3;  O  (  n  log  2  k  ?  6  n  )otherwise. Summingoverall(  d  ?  3)-simplicesinducedby  V  ,weobtain  ?  d  2    j E  j =  P    j E    j ,andhencetheupper bound. Toshowthattheresultistightfor  d  =3  ;k  =2,consideranestedsequenceof  n=  2pyramidsbased onthesame2-dimensionalconvex  n=  2-gon.Thesepyramidshaveatotalof  n  2  =  4triangularfaces,no twoofwhichhaveanon-trivialintersection. Itisanoutstandingopenproblemtodecidewhethertheorderofmagnitudeoftheabovebound canbeimprovede.g.for  d  =4  ;k  =2.However,modifyingtheproceduredescribedintheproof Theorem2.1,onecanshowthatthefollowingrelatedresultisasymptoticallytight.Thedetailsare lefttothereader. 
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks