427:, as the second chapter shows; the third concerns higher orders. The fourth chapter applies this theory to line segments, and includes a proof that the bounds proven using these tools are tight: there exist systems of line segments whose arrangement complexity matches the bounds on Davenport–Schinzel sequence length.
430:
The remaining chapters concern more advanced applications of these methods. Three chapters concern arrangements of curves in the plane, algorithms for arrangements, and higher-dimensional arrangements, following which the final chapter (comprising a large fraction of the book) concerns applications
455:
Although primarily aimed at researchers, this book (and especially its earlier chapters) could also be used as the textbook for a graduate course in its material. Reviewer Peter Hajnal calls it "very important to any specialist in computational geometry" and "highly recommended to anybody who is
116:, constrained by forbidding pairs of symbols from appearing in alternation more than a given number of times (regardless of what other symbols might separate them). In a Davenport–Schinzel sequence of order
330:
can have complexity that is only slightly superlinear. The book is about this family of results, both on bounding the lengths of
Davenport–Schinzel sequences and on their applications to discrete geometry.
296:
425:
258:
226:
364:
318:, can be only slightly longer than its number of distinct symbols. This phenomenon has been used to prove corresponding near-linear bounds on various problems in
384:
316:
194:
174:
154:
134:
334:
The first three chapters of the book provide bounds on the lengths of
Davenport–Schinzel sequences whose superlinearity is described in terms of the
97:
632:
617:
113:
627:
622:
86:
50:
436:
263:
389:
109:
559:
323:
231:
199:
505:
440:
335:
340:
456:
interested in this new topic at the border of combinatorics, geometry, and algorithm theory".
319:
82:
74:
32:
594:
533:
497:
105:
101:
568:
564:
537:
444:
432:
447:. The topic remains an active area of research and the book poses many open questions.
369:
301:
179:
159:
139:
119:
611:
156:. For instance, a Davenport–Schinzel sequence of order three could have two symbols
327:
78:
28:
366:. For instance, the length of a Davenport–Schinzel sequence of order three, with
488:
598:
550:
298:
would be forbidden. The length of such a sequence, for a given choice of
509:
528:
501:
439:, the construction of transversal lines through systems of objects,
20:
Davenport–Schinzel
Sequences and Their Geometric Applications
583:
Davenport–Schinzel
Sequences and Their Geometric Applications
555:
Davenport–Schinzel
Sequences and Their Geometric Applications
524:
Davenport–Schinzel
Sequences and Their Geometric Applications
484:
Davenport–Schinzel
Sequences and Their Geometric Applications
70:
Davenport–Schinzel
Sequences and Their Geometric Applications
108:, who applied them to certain problems in the theory of
392:
372:
343:
322:, for instance showing that the unbounded face of an
304:
266:
234:
202:
182:
162:
142:
122:
431:
of these combinatorial bounds to problems including
112:. They are finite sequences of symbols from a given
56:
46:
38:
24:
419:
378:
358:
310:
290:
252:
220:
188:
168:
148:
128:
136:, the longest allowed alternations have length
8:
19:
89:in 1995, with a paperback reprint in 2010.
482:Hajnal, Peter (December 1996), "Review of
18:
391:
371:
342:
303:
265:
233:
201:
181:
161:
141:
121:
465:
291:{\displaystyle x\dots y\dots x\dots y}
581:Nagy, Zoltán (July 1998), "Review of
7:
477:
475:
473:
471:
469:
420:{\displaystyle \Theta (n\alpha (n))}
393:
14:
196:that appear either in the order
260:, but longer alternations like
253:{\displaystyle y\dots x\dots y}
221:{\displaystyle x\dots y\dots x}
522:Brönnimann, Hervé, "Review of
414:
411:
405:
396:
353:
347:
1:
98:Davenport–Schinzel sequences
649:
359:{\displaystyle \alpha (n)}
336:inverse Ackermann function
87:Cambridge University Press
51:Cambridge University Press
599:10.1017/s0263574798241087
386:symbols, can be at most
437:nearest neighbor search
633:1995 non-fiction books
618:Combinatorics on words
451:Audience and reception
421:
380:
360:
312:
292:
254:
222:
190:
170:
150:
130:
110:differential equations
16:Book published in 1995
445:robot motion planning
422:
381:
361:
313:
293:
255:
223:
191:
171:
151:
131:
560:Mathematical Reviews
390:
370:
341:
302:
264:
232:
200:
180:
160:
140:
120:
77:. It was written by
553:(1996), "Review of
441:visibility problems
85:, and published by
21:
417:
376:
356:
308:
288:
250:
218:
186:
166:
146:
126:
628:Mathematics books
623:Discrete geometry
379:{\displaystyle n}
320:discrete geometry
311:{\displaystyle k}
189:{\displaystyle y}
169:{\displaystyle x}
149:{\displaystyle k}
129:{\displaystyle k}
83:Pankaj K. Agarwal
75:discrete geometry
66:
65:
33:Pankaj K. Agarwal
640:
602:
601:
578:
572:
571:
547:
541:
540:
519:
513:
512:
479:
433:Voronoi diagrams
426:
424:
423:
418:
385:
383:
382:
377:
365:
363:
362:
357:
317:
315:
314:
309:
297:
295:
294:
289:
259:
257:
256:
251:
227:
225:
224:
219:
195:
193:
192:
187:
175:
173:
172:
167:
155:
153:
152:
147:
135:
133:
132:
127:
106:Andrzej Schinzel
102:Harold Davenport
100:are named after
58:Publication date
22:
648:
647:
643:
642:
641:
639:
638:
637:
608:
607:
606:
605:
580:
579:
575:
549:
548:
544:
521:
520:
516:
502:10.1137/1038138
481:
480:
467:
462:
453:
388:
387:
368:
367:
339:
338:
300:
299:
262:
261:
230:
229:
198:
197:
178:
177:
158:
157:
138:
137:
118:
117:
95:
59:
17:
12:
11:
5:
646:
644:
636:
635:
630:
625:
620:
610:
609:
604:
603:
593:(4): 475–476,
573:
542:
514:
496:(4): 689–691,
464:
463:
461:
458:
452:
449:
416:
413:
410:
407:
404:
401:
398:
395:
375:
355:
352:
349:
346:
307:
287:
284:
281:
278:
275:
272:
269:
249:
246:
243:
240:
237:
217:
214:
211:
208:
205:
185:
165:
145:
125:
94:
91:
64:
63:
60:
57:
54:
53:
48:
44:
43:
40:
36:
35:
26:
15:
13:
10:
9:
6:
4:
3:
2:
645:
634:
631:
629:
626:
624:
621:
619:
616:
615:
613:
600:
596:
592:
588:
584:
577:
574:
570:
566:
562:
561:
556:
552:
546:
543:
539:
535:
531:
530:
525:
518:
515:
511:
507:
503:
499:
495:
491:
490:
485:
478:
476:
474:
472:
470:
466:
459:
457:
450:
448:
446:
442:
438:
434:
428:
408:
402:
399:
373:
350:
344:
337:
332:
329:
328:line segments
325:
321:
305:
285:
282:
279:
276:
273:
270:
267:
247:
244:
241:
238:
235:
215:
212:
209:
206:
203:
183:
163:
143:
123:
115:
111:
107:
103:
99:
92:
90:
88:
84:
80:
76:
73:is a book in
72:
71:
61:
55:
52:
49:
45:
41:
37:
34:
30:
27:
23:
590:
586:
582:
576:
558:
554:
545:
527:
523:
517:
493:
487:
483:
454:
429:
333:
96:
79:Micha Sharir
69:
68:
67:
29:Micha Sharir
551:Rivin, Igor
489:SIAM Review
324:arrangement
42:Mathematics
612:Categories
538:0834.68113
460:References
403:α
394:Θ
345:α
283:…
277:…
271:…
245:…
239:…
213:…
207:…
47:Publisher
587:Robotica
114:alphabet
569:1329734
510:2132953
567:
536:
529:zbMATH
508:
443:, and
93:Topics
25:Author
506:JSTOR
39:Genre
435:and
176:and
104:and
81:and
62:1995
31:and
595:doi
585:",
557:",
534:Zbl
526:",
498:doi
486:",
326:of
228:or
614::
591:16
589:,
565:MR
563:,
532:,
504:,
494:38
492:,
468:^
597::
500::
415:)
412:)
409:n
406:(
400:n
397:(
374:n
354:)
351:n
348:(
306:k
286:y
280:x
274:y
268:x
248:y
242:x
236:y
216:x
210:y
204:x
184:y
164:x
144:k
124:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.