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.

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Yingying Ren

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

2024

Blind as a bat: spatial perception without sight

Frederike Dümbgen

Among our five senses, we rely mostly on audition and vision to perceive an environment. Our ears are able to detect stimuli from all directions, especially from obstructed and far-away objects. Even in smoke, harsh weather conditions, or at night â situ ...

EPFL2021

Shapes From Echoes: Uniqueness From Point-to-Plane Distance Matrices

Martin Vetterli, Ivan Dokmanic, Miranda Krekovic

We study the problem of localizing a configuration of points and planes from the collection of point-to-plane distances. This problem models simultaneous localization and mapping from acoustic echoes as well as the & x201C;structure from sound & x201D; app ...

2020

An Improved Analysis of Local Search for Max-Sum Diversification

Friedrich Eisenbrand, Rico Zenklusen, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019

On Sets Defining Few Ordinary Circles

Frank de Zeeuw

An ordinary circle of a set P of n points in the plane is defined as a circle that contains exactly three points of P. We show that if P is not contained in a line or a circle, then P spans at least ordinary circles. Moreover, we determine the exact minimu ...

Springer2018

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

The present thesis deals with problems arising from discrete mathematics, whose proofs make use of tools from algebraic geometry and topology. The thesis is based on four papers that I have co-authored, three of which have been published in journals, and o ...

EPFL2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017

Omnidirectional bats, point-to-plane distances, and the price of uniqueness

Martin Vetterli, Ivan Dokmanic, Miranda Krekovic

We study simultaneous localization and mapping with a device that uses reflections to measure its distance from walls. Such a device can be realized acoustically with a synchronized collocated source and receiver; it behaves like a bat with no capacity for ...

Ieee2017

Distinct Distances on Algebraic Curves in the Plane

János Pach, Frank de Zeeuw

Let S be a set of n points in R-2 contained in an algebraic curve C of degree d. We prove that the number of distinct distances determined by S is at least c(d)n(4/3), unless C contains a line or a circle. We also prove the lower bound c(d)' min{m(2/3)n(2/ ...

Cambridge Univ Press2017

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that an ...

EPFL2017