Article Outline
- 1. Introduction
- 2. Optimal sets for (≤k)-edge vectors
- 3. A lower bound for (≤k)-facets in
- 4. Conclusions and open problems
- Acknowledgements
- References
排序方式： 共有32条查询结果，搜索用时 15 毫秒
21.
Aichholzer Cortés Demaine Dujmovic Erickson Meijer Overmars Palop Ramaswami Toussaint 《Discrete and Computational Geometry》2002,28(2):231-253
Abstract. A flipturn transforms a nonconvex simple polygon into another simple polygon by rotating a concavity 180° around the midpoint of its
bounding convex hull edge. Joss and Shannon proved in 1973 that a sequence of flipturns eventually transforms any simple polygon
into a convex polygon. This paper describes several new results about such flipturn sequences. We show that any orthogonal
polygon is convexified after at most n-5 arbitrary flipturns, or at most
well-chosen flipturns, improving the previously best upper bound of (n-1)!/2 . We also show that any simple polygon can be convexified by at most n
2
-4n+1 flipturns, generalizing earlier results of Ahn et al. These bounds depend critically on how degenerate cases are handled;
we carefully explore several possibilities. We prove that computing the longest flipturn sequence for a simple polygon is
NP-hard. Finally, we show that although flipturn sequences for the same polygon can have significantly different lengths,
the shape and position of the final convex polygon is the same for all sequences and can be computed in O(n log n) time. 相似文献
22.
23.
24.
Oswin Aichholzer 《Journal of Combinatorial Theory, Series A》2008,115(2):254-278
We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it on two prominent families of point sets, namely the so-called double circle and double chain. The latter has asymptotically n12nΘ(1) pointed pseudo-triangulations, which lies significantly above the maximum number of triangulations in a planar point set known so far. 相似文献
25.
Oswin Aichholzer Jesus Garcia David Orden Pedro Ramos 《Discrete and Computational Geometry》2007,38(1):1-14
We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the plane in general position. We show that
for
the number of (≤ k)-edges is at least
which, for
, improves the previous best lower bound in [12]. As a main consequence, we obtain a new lower bound on the rectilinear crossing
number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by n points in
the plane in general position. We show that the crossing number is at least
which improves the previous bound of
in [12] and approaches the best known upper bound
in [4]. The proof is based on a result about the structure of sets attaining the rectilinear crossing number, for which we
show that the convex hull is always a triangle. Further implications include improved results for small values of n. We extend
the range of known values for the rectilinear crossing number, namely by
and
. Moreover, we provide improved upper bounds on the maximum number of halving edges a point set can have. 相似文献
26.
Oswin Aichholzer Franz Aurenhammer Thomas Hackl 《Discrete and Computational Geometry》2007,38(4):701-725
We introduce the concept of pre-triangulations, a relaxation of triangulations that goes beyond the frequently used concept
of pseudo-triangulations. Pre-triangulations turn out to be more natural than pseudo-triangulations in certain cases. We show
that pre-triangulations arise in three different contexts: In the characterization of polygonal complexes that are liftable
to three-space in a strong sense, in flip sequences for general polygonal complexes, and as graphs of maximal locally convex
functions.
Research supported by the FWF Joint Research Project ‘Industrial Geometry’ S9205-N12. 相似文献
27.
Gray Code Enumeration of Plane Straight-Line Graphs 总被引：2，自引：0，他引：2
We develop Gray code enumeration schemes for geometric straight-line graphs in the plane. The considered graph classes include
plane graphs, connected plane graphs, and plane spanning trees. Previous results were restricted to the case where the underlying
vertex set is in convex position.
Research supported by the FWF Joint Research Project Industrial Geometry S9205-N12 and Projects MCYT-FEDER BFM2003-00368 and
Gen. Cat 2005SGR00692. 相似文献
28.
Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n=10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and k-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations. 相似文献
29.
30.
Oswin Aichholzer Jesús García David Orden Pedro Ramos 《European Journal of Combinatorics》2009,30(7):1568
In this paper we present two different results dealing with the number of (≤k)-facets of a set of points:
- 1. We give structural properties of sets in the plane that achieve the optimal lower bound of (≤k)-edges for a fixed 0≤k≤n/3−1; and
- 2. we show that, for k<n/(d+1), the number of (≤k)-facets of a set of n points in general position in is at least , and that this bound is tight in the given range of k.
1. Introduction
In this paper we deal with the problem of giving lower bounds to the number of (≤k)-facets of a set of points S. An oriented simplex with vertices at points of S is said to be a k-facet of S if it has exactly k points in the positive side of its affine hull. Similarly, the simplex is said to be an (≤k)-facet if it has at most k points in the positive side of its affine hull. If , a k-facet of S is usually named a k-edge.The number of k-facets of S is denoted by ek(S), and is the number of (≤k)-facets (the set S will be omitted when it is clear from the context). Giving bounds on these quantities, and on the number of the companion concept of k-sets, is one of the central problems in Discrete and Computational Geometry, and has a long history that we will not try to summarize here. Chapter 8.3 in [4] is a complete and up to date survey of results and open problems in the area.Regarding lower bounds for Ek(S), which is the main topic of this paper, the problem was first studied by Edelsbrunner et al. [6] due to its connections with the complexity of higher order Voronoi diagrams. In that paper it was stated that, in ,2. Optimal sets for (≤k)-edge vectors
Given , let us denote by the set of all (≤k)-edges of S; hence Ek(S) is the cardinality of . Throughout this section we consider . Recall that for a fixed such k, Ek(S) is optimal if . Recall also that, by definition, a j-edge has exactly j points of S in the positive side of its affine hull, which in this case is the open half-plane to the right of its supporting line.We start by giving a new, simple, and self-contained proof of the bound in Eq. (1), using a new technique which will be useful in the rest of the section. Although in this section they will be used in , the following notions are presented in for the sake of generality and in view of Section 3.Definition 1 [7] Let S be a set of n points and a family of sets in . A subset NS is called an -net of S (with respect to ) if for every such that |H∩S|>n we have that H∩N≠.Definition 2 A simplicial -net of is a set of d+1 vertices of the convex hull of S that are an -net of S with respect to closed half-spaces. A simplicial -net will be called a simplicial half-net.Lemma 3 Every set of n points has a simplicial half-net.Proof Let T be a triangle spanned by three vertices of the convex hull of S. An edge e of T is called good if the closed half-plane of its supporting line which contains the third vertex of T contains at least points from S. T is called good if it consists of three good edges. Clearly, the vertices of a good triangle T are a simplicial half-net of S; the vertices of T being of the convex hull implies that the intersection of S with a half-plane not containing any vertex of T lies in the complement of some of the three half-planes defined by the good edges.Let T be an arbitrary triangle spanned by vertices of the convex hull of S and assume that T is not good. Then observe that only one edge e of T is not good and let v be the vertex of T not incident to e. Choose a point v′ of the convex hull of S opposite to v with respect to e. Then e and v′ induce a triangle T′ in which e is a good edge. If T′ is a good triangle we are done. Otherwise we iterate this process. As the cardinalities of the subsets of vertices of S considered are strictly decreasing (the subsets being restricted by the half-plane induced by e), the process terminates with a good triangle. □Theorem 4 For every set S of n points and we have .Proof The proof goes by induction on n. From Lemma 3, we can guarantee the existence of T={a,b,c}S, an -net made up with vertices of the convex hull.Let S′=ST and consider an edge . We observe that T cannot be to the right of e: there are at least points on the closed half-plane to the left of e and that would contradict the definition of -net. Therefore, .If we denote by the set of (≤k)-edges of S incident to points in T, we have that- (a) .
- (b) A k-edge of S is either a (k−2)-edge of S′ or is incident to a point in T .