检索结果-内蒙古大学图书馆

Counting Convex and Non-Convex 4-Holes in a Point Set

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2021年第9期E104A卷 1094-1100页

作者： Sung, Young-Hun Bae, Sang Won Kyonggi Univ Div Comp Sci & Engn Suwon South Korea

In this paper, we present an algorithm that counts the number of empty quadrilaterals whose corners are chosen from a given set S of n points in general position. Our algorithm can separately count the number of convex or non-convex empty quadrilaterals in O(T) time, where T denotes the number of empty triangles in S. Note that T varies from Omega(n(2)) and O(n(3)) and the expected value of T is known to be Theta(n(2)) when the n points in S are chosen uniformly and independently at random from a convex and bounded body in the plane. We also show how to enumerate all convex and/or non-convex empty quadrilaterals in S in time proportional to the number of reported quadrilaterals, after O(T)-time preprocessing.

关键词： Erdos-Szekeres problem counting algorithm enumeration algorithm polygon discrete and computational geometry

来源：评论

学校读者我要写书评

暂无评论

ON THE ZONE THEOREM FOR HYPERPLANE ARRANGEMENTS

引用

SIAM JOURNAL ON COMPUTING 1993年第2期22卷 418-429页

作者： EDELSBRUNNER, H SEIDEL, R SHARIR, M UNIV CALIF BERKELEY DEPT ELECT ENGN & COMP SCI BERKELEY CA 94720 USA TEL AVIV UNIV SCH MATH SCI IL-69978 TEL AVIV ISRAEL NYU COURANT INST MATH SCI NEW YORK NY 10012 USA

The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n(d-1)). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d greater-than-or-equal-to 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.

关键词： discrete and computational geometry ARRANGEMENTS HYPERPLANES ZONES COUNTING FACES INDUCTION SWEEP

来源：评论

学校读者我要写书评

暂无评论

On Covering Problems of Rado

引用

ALGORITHMICA 2010年第3期57卷 538-561页

作者： Bereg, Sergey Dumitrescu, Adrian Jiang, Minghui Utah State Univ Dept Comp Sci Logan UT 84322 USA Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA

T. Rado conjectured in 1928 that if F is a finite set of axis-parallel squares in the plane, then there exists an independent subset a"aS dagger a"+/- of pairwise disjoint squares, such that a" covers at least 1/4 of the area covered by F. He also showed that the greedy algorithm (repeatedly choose the largest square disjoint from those previously selected) finds an independent set of area at least 1/9 of the area covered by F. The analogous question for other shapes and many similar problems have been considered by R. Rado in his three papers (in Proc. Lond. Math. Soc. 51:232-264, 1949;53:243-267, 1951;and J. Lond. Math. Soc. 42:127-130, 1968) on this subject. After 45 years, Ajtai (in Bull. Acad. Polon. Sci. S,r. Sci. Math. Astron. Phys. 21:61-63, 1973) came up with a surprising example disproving T. Rado's conjecture. We revisit Rado's problem and present improved upper and lower bounds for squares, disks, convex bodies, centrally symmetric convex bodies, and others, as well as algorithmic solutions to these variants of the problem.

关键词： discrete and computational geometry Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Characterization of Extremal Antipodal Polygons

引用

GRAPHS AND COMBINATORICS 2015年第2期31卷 321-333页

作者： Aichholzer, O. Caraballo, L. E. Diaz-Banez, J. M. Fabila-Monroy, R. Ochoa, C. Nigsch, P. Graz Univ Technol Inst Software Technol A-8010 Graz Austria Univ Seville Dept Matemat Aplicada 2 Seville Spain Inst Politecn Nacl Ctr Invest & Estudios Avanzados Dept Matemat Mexico City DF Mexico Univ Chile DCC Santiago Chile Graz Univ Technol A-8010 Graz Austria

Let be a set of points on a circle such that for each point also its antipodal (mirrored with respect to the circle center) point belongs to . A polygon of size is called antipodal if it consists of precisely one point of each antipodal pair of . We provide a complete characterization of antipodal polygons which maximize (minimize, respectively) the area among all antipodal polygons of . Based on this characterization, a simple linear time algorithm is presented for computing extremal antipodal polygons. Moreover, for the generalization of antipodal polygons to higher dimensions we show that a similar characterization does not exist.

关键词： Antipodal points Extremal area polygons discrete and computational geometry

来源：评论

学校读者我要写书评

暂无评论

ON THE ZONE THEOREM FOR HYPERPLANE ARRANGEMENTS

ON THE ZONE THEOREM FOR HYPERPLANE ARRANGEMENTS

引用

SYMP ON NEW RESULTS AND NEW TRENDS IN COMPUTER SCIENCE

作者： EDELSBRUNNER, H SEIDEL, R SHARIR, M Department of Computer Science University of Illinois at Urbana-Champaign Urbana 61801 IL United States Department of Electrical Engineering and Computer Science University of California Berkeley 94720 CA United States School of Mathematical Sciences Tel Aviv University Tel Aviv 69978 Israel Courant Institute of Mathematical Sciences New York University New York 10012 United States

The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(nd-1). This result is the basis of a time-... 详细信息

ISBN: (纸本)3540548696

The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n^d-1). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d ≥ 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. Our proof is based on an inductive argument, which also applies in the case of pseudo-hyperplane arrangements. We also briefly discuss the fallacies of the old proof along with some ways of partially saving that approach. © Springer-Verlag Berlin Heidelberg 1991.

关键词： discrete and computational geometry ARRANGEMENTS HYPERPLANES ZONES COUNTING FACES INDUCTION SWEEP

来源：评论

学校读者我要写书评

暂无评论

On the separability of quadrilaterals in the plane by translations and rotations

引用

BEITRAGE ZUR ALGEBRA UND GEOMETRIE-CONTRIBUTIONS TO ALGEBRA AND geometry 2017年第2期58卷 267-276页

作者： Houle, Michael E. Toussaint, Godfried T. Natl Inst Informat Tokyo Japan New York Univ Abu Dhabi Abu Dhabi U Arab Emirates

A proof is given that for all positive integers n >= 7 there exist sets of n non-overlapping quadrilaterals in the plane, such that no non-empty proper subset of these quadrilaterals can be separated from its complement, as one rigid object, by a single translation, without disturbing its complement. Furthermore, examples are given for which no single quadrilateral can be separated from the others by means of translations or rotations.

关键词： discrete and computational geometry Interlocking polygons Object mobility Collision avoidance Spatial planning Robotics

来源：评论

学校读者我要写书评

暂无评论

geometry in the Space of Persistence Modules

Geometry in the Space of Persistence Modules

引用

29th Annual Symposium on computational geometry (SoCG)

作者： de Silva, Vin Nanda, Vidit Pomona Coll Dept Math Claremont CA 91711 USA Univ Penn Dept Math Philadelphia PA 19104 USA

ISBN: (纸本)9781450320313

Topological persistence is, by now, an established paradigm for constructing robust topological invariants from point-cloud data: the data are converted into a filtered simplicial complex, the complex gives rise to a persistence module, and the module is described by a persistence diagram. In this paper, we study the geometry of the spaces of persistence modules and diagrams, with special attention to Cech and Rips complexes. The metric structures are determined in terms of interleaving maps between modules and matchings between diagrams. We show that the relationship between the Cech and Rips complexes is governed by certain 'coherence' conditions on the corresponding families of interleavings or matchings.

关键词： Theory Persistent Homology Embedding Theorem discrete and computational geometry

来源：评论

学校读者我要写书评

暂无评论

In the Land of Convex Polygons discrete geometry of Polygons

引用

RESONANCE-JOURNAL OF SCIENCE EDUCATION 2019年第5期24卷 583-595页

作者： Ninjbat, Uuganbaatar Gombodorj, Bayarmagnai Damba, Purevsuren Natl Univ Mongolia Ulaanbaatar Mongolia Stockholm Sch Stockholm Sweden Univ Tokyo Tokyo Japan Moscow State Pedag Univ Math Moscow Russia

This article shares some insights and observations that we gained while exploring the world of discrete and computational geometry. It discusses several results related to polygons and gives some historical remarks. Mathematical parts of our discussion support the view that in the land of polygons, convexity alone tells a lot, and quadrilaterals act as our main guides whenever we visit there.

关键词： Convex polygon discrete and computational geometry geometric inequality

来源：评论

学校读者我要写书评

暂无评论

On Covering Problems of Rado

引用

11th Scandinavian Workshop on Algorithm Theory (SWAT 2008)

ISBN: (纸本)3540699007

关键词： discrete and computational geometry Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

geometry in the Space of Persistence Modules 13

Geometry in the Space of Persistence Modules

引用

Annual Symposium on computational geometry

作者： Vin de Silva Vidit Nanda Department of Mathematics Pomona College Claremont California Department of Mathematics The University of Pennsylvania Philadelphia Pennsylvania

ISBN: (纸本)9781450320313

关键词： Persistent Homology Embedding Theorem discrete and computational geometry Environmental persistence geometry Persistence

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：