Property Testing with Geometric Queries

C. Sohler, A. Czumaj, Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01) (2001) 266–277.

Download
No fulltext has been uploaded.
Journal Article | English
Author
;
Abstract
This paper investigates geometric problems in the context of property testing algorithms. Property testing is an emerging area in computer science in which one is aiming at verifying whether a given object has a predetermined property or is “far” from any object having the property. Although there has been some research previously done in testing geometric properties, prior works have been mostly dealing with the study of combinatorial notion of the distance defining whether an object is “far” or it is “close”; very little research has been done for geometric notion of distance measures, that is, distance measures that are based on the geometry underlying input objects. The main objective of this work is to develop sound models to study geometric problems in the context of property testing. Comparing to the previous work in property testing, there are two novel aspects developed in this paper: geometric measures of being close to an object having the predetermined property, and the use of geometric data structures as basic primitives to design the testers. We believe that the second aspect is of special importance in the context of property testing and that the use of specialized data structures as basic primitives in the testers can be applied to other important problems in this area. We shall discuss a number of models that in our opinion fit best geometric problems and apply them to study geometric properties for three very fundamental and representative problems in the area: testing convex position, testing map labeling, and testing clusterability.
Publishing Year
Journal Title
Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01)
Page
266-277
LibreCat-ID

Cite this

Sohler C, Czumaj A. Property Testing with Geometric Queries. Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01). 2001:266-277. doi:10.1007/3-540-44676-1_22
Sohler, C., & Czumaj, A. (2001). Property Testing with Geometric Queries. Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01), 266–277. https://doi.org/10.1007/3-540-44676-1_22
@article{Sohler_Czumaj_2001, title={Property Testing with Geometric Queries}, DOI={10.1007/3-540-44676-1_22}, journal={Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01)}, author={Sohler, Christian and Czumaj, Artur}, year={2001}, pages={266–277} }
Sohler, Christian, and Artur Czumaj. “Property Testing with Geometric Queries.” Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01), 2001, 266–77. https://doi.org/10.1007/3-540-44676-1_22.
C. Sohler and A. Czumaj, “Property Testing with Geometric Queries,” Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01), pp. 266–277, 2001.
Sohler, Christian, and Artur Czumaj. “Property Testing with Geometric Queries.” Proceedings of the 9th Annual European Symposium on Algorithms (ESA`01), 2001, pp. 266–77, doi:10.1007/3-540-44676-1_22.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar