Finding structures on imprecise points

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


An imprecise point is a point in R^2 of which we do not know the location exactly; we only know for each point a region in R^2 containing it. On such a set of imprecise points, structures like the closest pair or convex hull are not uniquely defined. This leads us to study the following problem: Given a structure of interest, a set R of regions and a subset C ¿ R, we want to determine if it is possible to place a point in each region of R such that the points placed in regions of C form the structure of interest. We study this problem for the convex hull, with various types of regions. For each variant we either give a NP-hardness proof or a polynomial-time algorithm.
Original languageEnglish
Title of host publicationAbstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
EditorsJ. Vahrenhold
Place of PublicationDortmund
PublisherTechnische Universität Dortmund
Publication statusPublished - 2010
Event26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund
Duration: 22 Mar 201024 Mar 2010
Conference number: 26


Workshop26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated titleEuroCG 2010
Internet address


Dive into the research topics of 'Finding structures on imprecise points'. Together they form a unique fingerprint.

Cite this