14,966 research outputs found
Planar 3-SAT with a Clause/Variable Cycle
Get PDFIn the Planar 3-SAT problem, we are given a 3-SAT formula together with its incidence graph, which is planar, and are asked whether this formula is satisfiable. Since Lichtenstein's proof that this problem is NP-complete, it has been used as a starting point for a large number of reductions. In the course of this research, different restrictions on the incidence graph of the formula have been devised, for which the problem also remains hard.
In this paper, we investigate the restriction in which we require that the incidence graph is augmented by the edges of a Hamiltonian cycle that first passes through all variables and then through all clauses, in a way that the resulting graph is still planar. We show that the problem of deciding satisfiability of a 3-SAT formula remains NP-complete even if the incidence graph is restricted in that way and the Hamiltonian cycle is given. This complements previous results demanding cycles only through either the variables or clauses.
The problem remains hard for monotone formulas and instances with exactly three distinct variables per clause. In the course of this investigation, we show that monotone instances of Planar 3-SAT with three distinct variables per clause are always satisfiable, thus settling the question by Darmann, Döcker, and Dorn on the complexity of this problem variant in a surprising way
Order on Order Types
Get PDFGiven 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
Extending the Centerpoint Theorem to Multiple Points
Get PDFThe centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set P of n points in R^d, there is a point c, not necessarily from P, such that each halfspace containing c contains at least n/(d+1) points of P. Such a point c is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for the point set P. But what if we allow more than one representative? For example in one-dimensional data sets, often certain quantiles are chosen as representatives instead of the median.
We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set Q of (few) points such that every halfspace that contains one point of Q contains a large fraction of the points of P and every halfspace that contains more of Q contains an even larger fraction of P. This setting is comparable to the well-studied concepts of weak epsilon-nets and weak epsilon-approximations, where it is stronger than the former but weaker than the latter. We show that for any point set of size n in R^d and for any positive alpha_1,...,alpha_k where alpha_1 <= alpha_2 <= ... <= alpha_k and for every i,j with i+j <= k+1 we have that (d-1)alpha_k+alpha_i+alpha_j <= 1, we can find Q of size k such that each halfspace containing j points of Q contains least alpha_j n points of P. For two-dimensional point sets we further show that for every alpha and beta with alpha <= beta and alpha+beta <= 2/3 we can find Q with |Q|=3 such that each halfplane containing one point of Q contains at least alpha n of the points of P and each halfplane containing all of Q contains at least beta n points of P. All these results generalize to the setting where P is any mass distribution. For the case where P is a point set in R^2 and |Q|=2, we provide algorithms to find such points in time O(n log^3 n)
Douglas Alexander Stewart, poet, author and playwright
No full textDouglas Alexander Stewart, poet, author and playwrigh
Nontimber forest product opportunities in Alaska /
No full textAuthors: David Pilz, Susan J. Alexander, Jerry Smith, Robert Schroeder, and Jim Freed."May 2006."Cover title.Includes bibliographical references (p. 59-69).Mode of access: Internet
From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices
No full textA set P = H cup {w} of n+1 points in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on P, it suffices to know the so-called frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}.
We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles, and many more. Based on these formulas, the corresponding numbers of graphs can be computed efficiently.
Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of simplices spanned by H that contain w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions. The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d log n).
Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in R^d in time O(n^max(omega,k-2)) where omega = 2.373, even though the asymptotic number of facets may be as large as n^k
Author inscription in William Hazlitt, essayist and critic; selections from his writings, with a memoir, biographical and critical by Alexander Ireland
No full textAuthor's gift inscription, "To W. C. Hazlitt Esq with kind regards, from Alexr Ireland," with tipped-in review of the book.ASU Library edition has inscription from Ireland to Hazlitt [a child of William Hazlitt?].
Hazlitt , William, 1778-1830.
Ireland, Alexander, 1810-1894
The Author of the Alexander Romance
No full textThis paper, which is based on a portion of the introduction of the author’s edition of Il Romanzo di Alessandro (Mondadori: Fondazione Valla 2007), surveys the generic components of the Alexander Romance in an attempt to arrive at a definition of the work. The argument builds on Merkelbach’s categorisation of elements and uses Fusillo’s insight into the novel as an ‘encyclopaedic genre’ to propose that ‘historical novel’ is not, as Hägg contended, a misnomer for the work. The main components I discuss are: ‘life’; praxeis; chreiai; Cynic elements, including choliambic poetry and utopian perspectives; and the Egyptian aspects of the narrative. A concluding jeu d’esprit offers a characterisation of the putative author, his antecedents and his process of composition.Richard Stoneman was for 25 years editor for classics at Croom Helm and then Routledge. In 1997 he was appointed an Honorary Fellow in the department of classics, University of Exeter. After retiring from publishing in 2006 he has been pursuing his researches on the Alexander legends and teaching a course on the subject at Exeter. His Penguin translation of the Alexander Romance was published in 1991, and a volume of translated Legends of Alexander the Great appeared from Everyman in 1994. Also in 1994 he co-edited Greek Fiction with John Morgan. His edition of the Greek recensions of the Alexander Romance was published (volume I) by the Fondazione Valla in 2007 – volumes II and III will follow over the next few years – and his Alexander the Great: A Life in Legend appeared from Yale University Press in spring 2008. He is the author of a number of other books on Greek history and travel, and is writing a book on oracles
Author Correction: The dengue-specific immune response and antibody identification with machine learning
No full textCorrection to: npj Vaccineshttps://doi.org/10.1038/s41541-023-00788-7, published online 20 January 2024 In this article, the affiliation details for author Alexander Horst were incorrectly given as Alexander Horst1,2 but should have been Alexander Horst1 and other affiliations are renumbered. The original article has been corrected
Alexander Woollcott, author and stage actor
No full textAlexander Woollcott, author and stage actorTo order a reproduction, inquire about permissions, or for information about prices see:
http://www.lib.washington.edu/specialcollections/services/reproduction/reproduction
Please cite the Order NumberScanned at 600ppi with an Epson 20000 flatbed scanner. Image then rotated, cropped, level-adjusted, and sharpened using Photoshop CS3. Converted to a JPEG2000 image upon ingest into CONTENTdm
- …
