首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Order on Order Types
  • 本地全文:下载
  • 作者:Alexander Pilz ; Emo Welzl
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:34
  • 页码:285-299
  • DOI:10.4230/LIPIcs.SOCG.2015.285
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Given P and P', equally sized planar point sets in general position, we call a bijection from P to P' crossing-preserving if crossings of connecting segments in P are preserved in P' (extra crossings may occur in P'). If such a mapping exists, we say that P' crossing-dominates P, and if such a mapping exists in both directions, P and P' are called crossing-equivalent. The relation is transitive, and we have a partial order on the obtained equivalence classes (called crossing types or x-types). Point sets of equal order type are clearly crossing-equivalent, but not vice versa. Thus, x-types are a coarser classification than order types. (We will see, though, that a collapse of different order types to one x-type occurs for sets with triangular convex hull only.) We argue that either the maximal or the minimal x-types are sufficient for answering many combinatorial (existential or extremal) questions on planar point sets. Motivated by this we consider basic properties of the relation. We characterize order types crossing-dominated by points in convex position. Further, we give a full characterization of minimal and maximal abstract order types. Based on that, we provide a polynomial-time algorithm to check whether a point set crossing-dominates another. Moreover, we generate all maximal and minimal x-types for small numbers of points.
  • 关键词:point set; order type; planar graph; crossing-free geometric graph
国家哲学社会科学文献中心版权所有