1,721,268 research outputs found
Computing many faces in arrangements of lines and segments
No full textWe present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. pn The main new idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.A part of this work was done while the first and third authors were visiting Charles University and while the first author was visiting Utrecht University. The first author has been supported by National Science Foundation Grant CCR-93-01259 and an NYI aword. The second author has been supported by Charles University grant No. 351 and Czech Republic Grant GACR 201/93/2167. The third author has been supported by the Netherlands' Organization for Scientific Research (NWO) and partially supported by ESPRIT Basic Research Action No. 7141 (project ALCOM 2:Algorithms and Complexity)
A deterministic algorithm for the three-dimensional diameter problem
No full textWe give a deterministic algorithm for computing the diameter of an n-point set in three dimensions with O(n log(c)n) running time, where c is a constant.This research was supported by the Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT Basic Research Action No. 7141 (project ALCOM II). J.M. acknowledges support by Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University
ON RAY SHOOTING IN CONVEX POLYTOPES
No full textLet P be a convex polytope with n facets in the Euclidean space of a (small) fixed dimension d. We consider the membership problem for P (given a query point, decide whether it lies in P) and the ray shooting problem in P (given a query ray originating inside P, determine the first facet of P hit by it). It was shown in [AM2] that a data structure for the membership problem satisfying certain mild assumptions can also be used for the ray shooting problem, with a logarithmic overhead in query time, Here we show that some specific data structures for the membership problem can be used for ray shooting in a more direct way, reducing the overhead in the query time and eliminating the use of parametric search. We also describe an improved static solution for the membership problem, approaching the conjectured lower bounds more tightly
No Helly theorem for stabbing translates by lines in R-3
No full textFor each n > 2 we construct a convex body K subset of R-3 and a finite family F of disjoint translates of K such that any n - 1 members F admit a line transversal, but F has no line transversal
Constructing levels in arrangements and higher order Voronoi diagrams
Full text linkWe give simple randomized incremental algorithms for computing the Amk-level in an arrangement of n lines in the plane or in an arrangement of n planes in . The expected running time of our algorithms is for the planarcase and O(nk2 + n log3n) for the three-dimensional case. Both bounds are optimal unless k is very small. The algorithm generalizes to computing the Amk-level in an arrangement of discs or x-monotone Jordan curves in the plane. Our approach can also compute the k-level; this yields a randomized algorithm for computing the order-k Voronoi diagram of n points in the plane in expected time O(k(n-k)log n + n log3n)
Quantum sign permutation polytopes
No full textConvex polytopes are convex hulls of point sets in the n-dimensional space E n that generalize 2-dimensional convex polygons and 3-dimensional convex polyhedra. We concentrate on the class of n-dimensional polytopes in E n called sign permutation polytopes. We characterize sign permutation polytopes before relating their construction to constructions over the space of quantum density matrices. Finally, we consider the problem of state identication and show how sign permutation polytopes may be useful in addressing issues of robustness
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
