Hasil untuk "cs.CG"

Zoltán Kovács

We give an alternative proof of the statement, by using elimination from algebraic geometry, that the only set $S\subset\mathbb{R}^2$, $\left|S\right|=6$ such that all subsets that form a triangle are isosceles triangles, is the regular pentagon with its center. Our proof can be extended to answer some related questions raised by Erdős.

José-Miguel Díaz-Báñez

In this paper, we present a series of mathematical problems which throw interesting lights on flamenco music. More specifically, these are problems in discrete and computational mathematics suggested by an analytical (not compositional) examination of flamenco ``cante'' (singing). As a consequence, since the problems are taken from a culturally specific context, the examples can make more effective mathematics education.

Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick

We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.

Martin Wilhelm

Accuracy-driven computation is a strategy widely used in exact-decisions number types for robust geometric algorithms. This work provides an overview on the usage of error bounds in accuracy-driven computation, compares different approaches on the representation and computation of these error bounds and points out some caveats. The stated claims are supported by experiments.

Lucas Moutinho Bueno

We propose an algorithm to create a 3-colorable Delaunay Triangulation. The input of the problem we are trying to solve is a set X of n twodimensional points. The output is a 3-colorable two-dimensional Delaunay triangulation T for X U Y , where Y is a set of m new points. We want to m be as few as possible.

Mathieu Carriere, Raul Rabadan

In this article, we show how the recent statistical techniques developed in Topological Data Analysis for the Mapper algorithm can be extended and leveraged to formally define and statistically quantify the presence of topological structures coming from biological phenomena in datasets of CCC contact maps.

Adil Erzin

In this paper, we propose several regular covers with identical sectors that observe the strip in the same direction, and we carried out their analysis, which allows choosing the best coverage model and the best parameters of the sector.

Breno Piva, Cid C. de Souza

This paper presents a counterexample for the approximation algorithm proposed by Durocher and Mehrabi [1] for the general problem of finding a rectangular partition of a rectilinear polygon with minimum stabbing number.

Mohammad Ali Abam, Mark de Berg, Mohammad Javad Rezaei Seraji

We show that there exists a geodesic spanner with almost linear number of edges.

Nina Amenta, Tamal K. Dey

The change in the normal between any two nearby points on a closed, smooth surface is bounded with respect to the local feature size (distance to the medial axis). An incorrect proof of this lemma appeared as part of the analysis of the "crust" algorithm of Amenta and Bern.

Jacek Skryzalin, Gunnar Carlsson

We extend the results of Adcock, Carlsson, and Carlsson by constructing numeric invariants from the computation of a multidimensional persistence module as given by Carlsson, Singh, and Zomorodian.

Bodhayan Roy

Given a 3-SAT formula, a graph can be constructed in polynomial time such that the graph is a point visibility graph if and only if the 3-SAT formula is satisfiable. This reduction establishes that the problem of recognition of point visibility graphs is NP-hard.

David Simmons, Yaar Solomon

We present concrete constructions of discrete sets in $\mathbb{R}^d$ ($d\ge 2$) that intersect every aligned box of volume $1$ in $\mathbb{R}^d$, and which have optimal growth rate $O(T^d)$.

Dmitry Kamenetsky, Tristrom Cooke

We present a new type of polyominoes that can have transparent squares (holes). We show how these polyominoes can tile rectangles and we categorise them according to their tiling ability. We were able to categorise all but 6 polyominoes with 5 or fewer visible squares.

Alexis Beingessner, Michiel Smid

We consider the problem of taking an opaque forest and determining the regions that are covered by it. We provide a tight upper bound on the complexity of this problem, and an algorithm for computing this area, which is worst-case optimal.

Zbigniew Gołębiewski, Filip Zagórski

In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping <underline>fair</underline> coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for <underline>fair</underline> coin).

Jacek Cichoń, Zbigniew Gołębiewski

In the paper we discuss a technology based on Bernstein polynomials of asymptotic analysis of a class of binomial sums that arise in information theory. Our method gives a quick derivation of required sums and can be generalized to multinomial distributions. As an example we derive a formula for the entropy of multinomial distributions. Our method simplifies previous work of Jacquet, Szpankowski and Flajolet from 1999.

Patrick Bindjeme, james Allen fill

In a continuous-time setting, Fill (2012) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by $\texttt{QuickSort}$, when centered by subtracting the mean and scaled by dividing by time, has a limiting distribution, but proved little about that limiting random variable $Y$—not even that it is nondegenerate. We establish the nondegeneracy of $Y$. The proof is perhaps surprisingly difficult.

Philippe Jacquet, Wojciech Szpankowski

String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define $\textit{joint string complexity}$ as the set of words that are common to both strings. We also relax this definition and introduce $\textit{joint semi-complexity}$ restricted to the common words appearing at least twice in both strings. String complexity finds a number of applications from capturing the richness of a language to finding similarities between two genome sequences. In this paper we analyze joint complexity and joint semi-complexity when both strings are generated by a Markov source. The problem turns out to be quite challenging requiring subtle singularity analysis and saddle point method over infinity many saddle points leading to novel oscillatory phenomena with single and double periodicities.

Isabelle Debled-Rennesson, Maurice Margenstern

In this paper, we look at the possibility to implement the algorithm to construct a discrete line devised by the first author in cellular automata. It turns out that such an implementation is feasible.