共查询到20条相似文献,搜索用时 9 毫秒
1.
We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(knε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(nε). 相似文献
2.
Agnieszka Siluszyk 《Mathematics in Computer Science》2017,11(3-4):457-467
The existence of a central configuration of 2n bodies located on two concentric regular n-gons with the polygons which are homotetic or similar with an angle equal to \(\frac{\pi }{n}\) and the masses on the same polygon, are equal, has proved by Elmabsout (C R Acad Sci 312(5):467–472, 1991). Moreover, the existence of a planar central configuration which consists of 3n bodies, also situated on two regular polygons, the interior n-gon with equal masses and the exterior 2n-gon with masses on the 2n-gon alternating, has shown by author. Following Smale (Invent Math 11:45-64, 1970), we reduce this problem to one, concerning the critical points of some effective-type potential. Using computer assisted methods of proof we show the existence of ten classes of such critical points which corresponds to ten classes of central configurations in the planar six-body problem. 相似文献
3.
4.
Tim Penttila 《Journal of Geometry》2003,76(1-2):233-255
We survey the known hyperovals in .
We then survey the relationship of the study of configurations of ovals
in called augmented fans to that
of ovoids of , flocks of the
quadratic cone of , flocks of a
translation oval cone of and
spreads of certain generalised quadrangles of order. We also consider the configurations of ovals in called herds and their
relationship with flocks of the quadratic cone of. 相似文献
5.
6.
A configuration of lattice vectors is supernormal if it contains a Hilbert basis for every pointed cone spanned by a subset. We study such configurations from various perspectives, including triangulations, integer programming and Gröbner bases. Our main result is a bijection between virtual chambers of the configuration and virtual initial ideals of the associated binomial ideal. 相似文献
7.
In the present paper we continue the work begun by Sauer, Perles, Shelah and Anstee on forbidden configurations of 0–1 matrices. We give asymptotically exact bounds for all possible 2 × l forbidden submatrices and almost all 3 × l ones. These bounds are improvements of the general bounds, or else new constructions show that the general bound is best possible. It is interesting to note that up to the present state of our knowledge every forbidden configuration results in polynomial asymptotic. 相似文献
8.
9.
V. F. Mazurovskii 《Journal of Mathematical Sciences》1990,52(1):2825-2832
In this paper we give a classification of nonsingular configurations of 6 lines of the space RP3 with respect to right isotopy (in the course of a rigid isotopy the lines remain pairwise disjoint lines) and prove that up to rigid isotopies nonsingular configurations of 6 lines are not determined by the linking coefficients.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 167, pp. 121–134, 1988. 相似文献
10.
By means of the Cayley Trick the problem of enumerating all regular fine mixed subdivisions is reduced to enumerating all regular triangulations. The set of all regular triangulations is well understood thanks to the bijection with the vertices of the secondary polytope. However, since we are only interested in the configurations of mixed cells in a mixed subdivision, we want to avoid dealing with other cells. We propose an operator derived from the bistellar flip for regular triangulations to modify a mixed-cell configuration. Received June 30, 1997, and in revised form December 1, 1997. 相似文献
11.
Leah Wrenn Berman 《Discrete and Computational Geometry》2011,46(3):447-470
A geometric (q,k)-configuration is a collection of points and straight lines in the Euclidean plane in which each point lies on q lines and each line passes through k points. We say a (q,k)-configuration is highly incident when one (or both) of q or k is strictly greater than 4. In this paper, two simple lemmas are used to construct infinite classes of (2q,2k)-configurations for any q,k≥2; the resulting configurations have non-trivial dihedral symmetry. In particular, this construction produces the only known
infinite class of symmetric 6-configurations. 相似文献
12.
There are ten configurations of two bowties that can arise in a bowtie system. We determine a basis for configurations of two bowties in both balanced and general bowtie systems. We also determine the avoidance spectrum for the three most compact configurations of two bowties. 相似文献
13.
Equilibrium configurations of point charges with Coulomb interaction on a circle, line segment, and a system of three concentric circles is discussed. A characterization of stable electrostatic configurations with a few points is obtained.
相似文献14.
Zvonko Čerin 《Journal of Geometry》2007,87(1-2):14-30
This paper explores equilateral triangles XYZ with vertices on sidelines of a given triangle ABC such that one side of XYZ is parallel to the corresponding side of ABC. There are six such triangles. They have many interesting properties which we investigate using trilinear coordinates. Our
results improve and add to the earlier results of Blas Herrera Gómez about these configurations. We obtain new characterizations
of several central points of the triangles and identify interesting pairs of triangles that are homologic (or perspective)
and orthologic. The recognition of the Darboux cubic of a triangle is also accomplished in these configurations. Triples of
circles intersecting in a point and six points on a conic also appear.
相似文献
15.
Steve Butler Ron Graham Gerhard Guettler Colin Mallows 《Discrete and Computational Geometry》2010,44(3):487-507
An Apollonian configuration of circles is a collection of circles in the plane with disjoint interiors such that the complement
of the interiors of the circles consists of curvilinear triangles. One well-studied method of forming an Apollonian configuration
is to start with three mutually tangent circles and fill a curvilinear triangle with a new circle, then repeat with each newly
created curvilinear triangle. More generally, we can start with three mutually tangent circles and a rule (or rules) for how
to fill a curvilinear triangle with circles. 相似文献
16.
Richard P. Anstee Christina Koch Miguel Raggi Attila Sali 《Graphs and Combinatorics》2014,30(6):1325-1349
A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say that a (0,1)-matrix A has F as a configuration if there is a submatrix of A which is a row and column permutation of F (trace is the set system version of a configuration). Let \({\|A\|}\) denote the number of columns of A. We define \({{\rm forb}(m, F) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration F. We extend this to a family \({\mathcal{F} = \{F_1, F_2, \ldots , F_t\}}\) and define \({{\rm forb}(m, \mathcal{F}) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration \({F \in \mathcal{F}\}}\) . We consider products of matrices. Given an m 1 × n 1 matrix A and an m 2 × n 2 matrix B, we define the product A × B as the (m 1 + m 2) × n 1 n 2 matrix whose columns consist of all possible combinations obtained from placing a column of A on top of a column of B. Let I k denote the k × k identity matrix, let \({I_k^{c}}\) denote the (0,1)-complement of I k and let T k denote the k × k upper triangular (0,1)-matrix with a 1 in position i, j if and only if i ≤ j. We show forb(m, {I 2 × I 2, T 2 × T 2}) is \({\Theta(m^{3/2})}\) while obtaining a linear bound when forbidding all 2-fold products of all 2 × 2 (0,1)-simple matrices. For two matrices F, P, where P is m-rowed, let \({f(F, P) = {\rm max}_{A} \{\|A\| \,:\,A}\) is m-rowed submatrix of P with no configuration F}. We establish f(I 2 × I 2, I m/2 × I m/2) is \({\Theta(m^{3/2})}\) whereas f(I 2 × T 2, I m/2 × T m/2) and f(T 2 × T 2, T m/2 × T m/2) are both \({\Theta(m)}\) . Additional results are obtained. One of the results requires extensive use of a computer program. We use the results on patterns due to Marcus and Tardos and generalizations due to Klazar and Marcus, Balogh, Bollobás and Morris. 相似文献
17.
V. K. Medvedev 《Ukrainian Mathematical Journal》1997,49(10):1516-1532
We find necessary conditions that should be imposed on a number n for the existence of an arbitrary configuration in at least one finite projective plane of order n.
Kiev University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 10, pp. 1345–1359, October, 1997. 相似文献
18.
W.D Wallis 《Journal of Combinatorial Theory, Series A》1973,15(1):115-119
We show that the existence of a maximal arc in a finite projective plane implies the existence of certain block designs and partial geometries. The block designs obtained have interesting resolvability properties. 相似文献
19.
Fedde J. Terpstra 《Mathematische Annalen》1958,135(4):315-339
20.
For fiber-commutative coherent configurations,we show that Krein parameters can be defined essentially uniquely.As a consequence,the general Krein condition reduces to positive semidefiniteness of finitely many matrices determined by the parameters of a coherent configuration.We mention its implications in the coherent configuration defined by a generalized quadrangle.We also simplify the absolute bound using the matrices of Krein parameters. 相似文献