Publication

Delaunay Graphs of Point Sets in the Plane With Respect to Axis-Parallel Rectangles

Related publications (43)

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.

Inference of Mobility Patterns via Spectral Graph Wavelets

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Modern data processing tasks frequently involve structured data, for example signals defined on the vertex set of a weighted graph. In this paper, we address the problem of inference of mobility patterns from data defined on geographical graphs based on sp ...

2013

On the Performance of Percolation Graph Matching

Matthias Grossglauser, Lyudmila Yartseva

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...

ACM2013

The flip-graph of the 4-dimensional cube is connected

Lionel Pournin

Flip-graph connectedness is established here for the vertex set of the 4-dimensional cube. It is found as a consequence, that this vertex set admits 92487256 triangulations, partitioned into 247451 symmetry classes. ...

Springer-Verlag2013

Two and a half billion years of distance research

János Pach, Filip Moric

In a seminal paper published in 1946, Erd ̋os initiated the investigation of the distribution of distances generated by point sets in metric spaces. In spite of some spectacular par- tial successes and persistent attacks by generations of mathe- maticians, ...

2013

Large simplices determined by finite point sets

János Pach, Filip Moric

Given a set P of n points in ℝd, let d1 > d2 >...denote all distinct inter-point distances generated by point pairs in P. It was shown by Schur, Martini, Perles, and Kupitz that there is at most oned-dimensional regular simplex of edge length d1 whos ...

Springer-Verlag2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

Fabrication-aware Design with Intersecting Planar Pieces

Mark Pauly, Yuliy Gennadievich Schwartzburg

We propose a computational design approach to generate 3D models composed of interlocking planar pieces. We show how intricate 3D forms can be created by sliding the pieces into each other along straight slits, leading to a simple construction that does no ...

Blackwell Publishing2013

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

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

2012

String graphs and incomparability graphs

János Pach

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,

2012