Publication

Distinct distances between points and lines

Related publications (32)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013

Tangles and Degenerate Tangles

Andres Jacinto Ruiz Vargas

We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...

Springer Berlin Heidelberg2013

Consistent Digital Line Segments

Doemoetoer Palvoelgyi

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order o ...

2012

First impressions: Gait cues drive reliable trait judgements

John Christian Thoresen

Personality trait attribution can underpin important social decisions and yet requires little effort; even a brief exposure to a photograph can generate lasting impressions. Body movement is a channel readily available to observers and allows judgements to ...

Elsevier Science Bv2012

On the connectivity of visibility graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibil ...

2011

Tangencies between families of disjoint regions in the plane

János Pach

Let C be a family of n convex bodies in the plane, which can be decomposed into k subfamilies of pairwise disjoint sets. It is shown that the number of tangencies between the members of C is at most O(kn), and that this bound cannot be improved. If we only ...

2010

Computing in Social Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Kévin Clément Huguenin, Andrei Giurgiu

This paper defines the problem of Scalable Secure Computing in a Social network: we call it the S-3 problem. In short, nodes, directly reflecting on associated users, need to compute a function f : V -> U of their inputs in a set of constant size, in a sca ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

The Complexity of Distinguishing Distributions

Serge Vaudenay, Thomas Baignères

Cryptography often meets the problem of distinguishing distributions. In this paper we review techniques from hypothesis testing to express the advantage of the best distinguisher limited to a given number of samples. We link it with the Chernoff informati ...

Springer2008

Tangent Vector Kernels for Invariant Image Classification with SVMs

Samy Bengio, Alexei Pozdnoukhov

This paper presents an application of the general sample-to-object approach to the problem of invariant image classification. The approach results in defining new SVM kernels based on tangent vectors that take into account prior information on known invari ...

2004

Tangent Vector Kernels for Invariant Image Classification with SVMs

Samy Bengio, Alexei Pozdnoukhov

IDIAP2003