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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Vol/bind	8486
Sider (fra-til)	110-119
Antal sider	10
ISSN	0302-9743
Status	Udgivet - 2014

Emneord

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

Citationsformater

@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

Emneord

Fingeraftryk

Citationsformater