Indexed Geometric Jumbled Pattern Matching

Stephane Durocher; Robert Fraser; Travis Gagie; Debajyoti Mondal; Matthew Skala; Sharma Thankachan

Indexed Geometric Jumbled Pattern Matching

Stephane Durocher, Robert Fraser, Travis Gagie, Debajyoti Mondal, Matthew Skala, Sharma Thankachan

Algorithms

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

We consider how to preprocess n colored points in the plane such that later, given a multiset of colors, we can quickly find an axis-aligned rectangle containing a subset of the points with exactly those colors, if one exists.

Original language	English
Book series	Lecture Notes in Computer Science
Volume	8486
Pages (from-to)	110-119
Number of pages	10
ISSN	0302-9743
Publication status	Published - 2014

Keywords

Computational geometry
Data structures
Color query problem
Range searching
Plane point location

Cite this

@article{5a32e2fb5a7146e2bcb6209800314a24,

title = "Indexed Geometric Jumbled Pattern Matching",

abstract = "We consider how to preprocess n colored points in the plane such that later, given a multiset of colors, we can quickly find an axis-aligned rectangle containing a subset of the points with exactly those colors, if one exists.",

keywords = "Computational geometry, Data structures, Color query problem, Range searching, Plane point location, Computational geometry, Data structures, Color query problem, Range searching, Plane point location",

author = "Stephane Durocher and Robert Fraser and Travis Gagie and Debajyoti Mondal and Matthew Skala and Sharma Thankachan",

year = "2014",

language = "English",

volume = "8486",

pages = "110--119",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - JOUR

T1 - Indexed Geometric Jumbled Pattern Matching

AU - Durocher, Stephane

AU - Fraser, Robert

AU - Gagie, Travis

AU - Mondal, Debajyoti

AU - Skala, Matthew

AU - Thankachan, Sharma

PY - 2014

Y1 - 2014

N2 - We consider how to preprocess n colored points in the plane such that later, given a multiset of colors, we can quickly find an axis-aligned rectangle containing a subset of the points with exactly those colors, if one exists.

AB - We consider how to preprocess n colored points in the plane such that later, given a multiset of colors, we can quickly find an axis-aligned rectangle containing a subset of the points with exactly those colors, if one exists.

KW - Computational geometry

KW - Data structures

KW - Color query problem

KW - Range searching

KW - Plane point location

KW - Computational geometry

KW - Data structures

KW - Color query problem

KW - Range searching

KW - Plane point location

M3 - Journal article

SN - 0302-9743

VL - 8486

SP - 110

EP - 119

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

Indexed Geometric Jumbled Pattern Matching

Abstract

Keywords

Fingerprint

Cite this